;SIZE 11
;VSP 6
;TOPMAR 0
;BOTMAR 0
;LFTMAR 0
;SKIP 1
;SQUISH
;KSET FONTS;25FR1 KST,FONTS;20FG KST,FONTS;30VRB KST,FONTS;40VR KST,,
AI:GLS;NNTJ6 10.6











␈↓ ∧λ␈↓αMASSACHUSETTS INSTITUTE OF TECHNOLOGY␈↓
␈↓ ∧0␈↓αARTIFICIAL INTELLIGENCE LABORATORY␈↓

␈↓ αλAI Memo No.␈↓ εx␈↓ 
_December 1975

␈↓ ε&␈↓βSCHEME␈↓

␈↓ βL␈↓αAN INTERPRETER FOR EXTENDED LAMBDA CALCULUS␈↓

␈↓ εhby

␈↓ ∧ Gerald Jay Sussman and Guy Lewis Steele Jr.



␈↓ αλAbstract:
␈↓ αhInspired by ACTORS [Greif and Hewitt] [Smith and Hewitt], we have
␈↓ αλimplemented an interpreter for a LISP-like language, SCHEME, based on the
␈↓ αλlambda calculus [Church], but extended for side effects, multiprocessing, and
␈↓ αλprocess synchronization.  The purpose of this implementation is tutorial.  We
␈↓ αλwish to:

␈↓ αλ(1) alleviate the confusion caused by Micro-PLANNER, CONNIVER, etc.  by
␈↓ αλclarifying the embedding of non-recursive control structures in a recursive
␈↓ αλhost language like LISP.
␈↓ αλ(2) explain how to use these control structures, independent of such issues as
␈↓ αλpattern matching and data base manipulation.
␈↓ αλ(3) have a simple concrete experimental domain for certain issues of
␈↓ αλprogramming semantics and style.

␈↓ αλThis paper is organized into sections.  The first section is a short
␈↓ αλ"reference manual" containing specifications for all the unusual features of
␈↓ αλSCHEME.  Next, we present a sequence of programming examples which illustrate
␈↓ αλvarious programming styles, and how to use them.  This will raise certain
␈↓ αλissues of semantics which we will try to clarify with lambda calculus in the
␈↓ αλthird section.  In the fourth section we will give a general discussion of the
␈↓ αλissues facing an implementor of an interpreter for a language based on lambda
␈↓ αλcalculus.  Finally, we will present a completely annotated interpreter for
␈↓ αλSCHEME, written in MacLISP [Moon], to acquaint programmers with the tricks of
␈↓ αλthe trade of implementing non-recursive control structures in a recursive
␈↓ αλlanguage like LISP.



␈↓ αλThis report describes research done at the Artificial Intelligence Laboratory
␈↓ αλof the Massachusetts Institute of Technology.  Support for the laboratory's
␈↓ αλartificial intelligence research is provided in part by the Advanced Research
␈↓ αλProjects Agency of the Department of Defense under Office of Naval Research
␈↓ αλcontract



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εr1␈↓ λ8The SCHEME Reference Manual␈↓'β␈↓'α␈↓








␈↓ αλSection 1: The SCHEME Reference Manual



␈↓ αhSCHEME is essentially a full-funarg LISP.  LAMBDA expressions need not
␈↓ αλbe QUOTEd, FUNCTIONed, or *FUNCTIONed when passed as arguments or returned as
␈↓ αλvalues; they will evaluate to closures of themselves.
␈↓ αhAll LISP functions (i.e., EXPRs, SUBRs, and LSUBRs, but ␈↓¬␈↓'β␈↓'α FEXPRs,
␈↓ αλFSUBRs, or MACROs) are primitive operators in SCHEME, and have the same
␈↓ αλmeaning as they have in LISP.  Like LAMBDA expressions, primitive operators
␈↓ αλand numbers are self-evaluating (they evaluate to trivial closures of
␈↓ αλthemselves).
␈↓ αhThere are a number of special primitives known as AINTs which are to
␈↓ αλSCHEME as FSUBRs are to LISP.  We will enumerate them here.

␈↓ αλIF
␈↓ αhThis is the primitive conditional operator.  It takes three arguments.
␈↓ αλIf the first evaluates to non-NIL, it evaluates the second expression, and
␈↓ αλotherwise the third.

␈↓ αλQUOTE
␈↓ αhAs in LISP, this quotes the argument form so that it will be passed
␈↓ αλverbatim as data.  The abbreviation "'FOO" may be used instead of "(QUOTE
␈↓ αλFOO)".

␈↓ αλDEFINE
␈↓ αhThis is analogous to the MacLISP DEFUN primitive (but note that the
␈↓ αλLAMBDA must appear explicitly!).  It is used for defining a function in the
␈↓ αλ"global environment" permanently, as opposed to LABELS (see below), which is
␈↓ αλused for temporary definitions in a local environment.  DEFINE takes a name
␈↓ αλand a lambda expression;  it closes the lambda expression in the global
␈↓ αλenvironment and stores the closure in the LISP value cell of the name (which
␈↓ αλis a LISP atom).

␈↓ αλLABELS
␈↓ αhWe have decided not to use the traditional LABEL primitive in this
␈↓ αλinterpreter because it is difficult to define several mutually recursive
␈↓ αλfunctions using only LABEL.  The solution, which Hewitt [Smith and Hewitt]
␈↓ αλalso uses, is to adopt an ALGOLesque block syntax:

␈↓ αλ␈↓ αh␈↓↓(LABELS <function definition list> <expression>)␈↓

␈↓ αλThis has the effect of evaluating the expression in an environment where all
␈↓ αλthe functions are defined as specified by the definitions list.  Furthermore,
␈↓ αλthe functions are themselves closed in that environment, and not in the outer
␈↓ αλenvironment; this allows the functions to call themselves ␈↓&and each other␈↓'β␈↓'α
␈↓ αλrecursively.  For example, consider a function which counts all the atoms in a
␈↓ αλlist structure recursively to all levels, but which doesn't count the NILs
␈↓ αλwhich terminate lists (but NILs in the CAR of some list count).  In order to
␈↓ αλperform this we use two mutually recursive functions, one to count the car and


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εr2␈↓ λ8The SCHEME Reference Manual␈↓'β␈↓'α␈↓








␈↓ αλone to count the cdr, as follows:

␈↓ αλ␈↓ αh␈↓↓(DEFINE COUNT␈↓
␈↓ β_␈↓↓(LAMBDA (L)␈↓
␈↓ βH␈↓↓(LABELS ((COUNTCAR␈↓
␈↓ ∧@␈↓↓(LAMBDA (L)␈↓
␈↓ ∧p␈↓↓(IF (ATOM L) 1␈↓
␈↓ ¬ ␈↓↓(+ (COUNTCAR (CAR L))␈↓
␈↓ ¬D␈↓↓(COUNTCDR (CDR L))))))␈↓
␈↓ ∧4␈↓↓(COUNTCDR␈↓
␈↓ ∧@␈↓↓(LAMBDA (L)␈↓
␈↓ ∧p␈↓↓(IF (ATOM L)␈↓
␈↓ ¬ ␈↓↓(IF (NULL L) 0 1)␈↓
␈↓ ¬ ␈↓↓(+ (COUNTCAR (CAR L))␈↓
␈↓ ¬D␈↓↓(COUNTCDR (CDR L)))))))␈↓
␈↓ βl␈↓↓(COUNTCDR L))))␈↓ ¬h␈↓ εH;Note: COUNTCDR is defined here.␈↓


␈↓ αλASET
␈↓ αhThis is the side effect primitive.  It is analogous to the LISP function
␈↓ αλSET.  For example, to define a ␈↓&cell␈↓'β␈↓'α [Smith and Hewitt], we may use ASET as
␈↓ αλfollows:

␈↓ αλ␈↓ αh␈↓↓(DEFINE CONS-CELL␈↓
␈↓ β_␈↓↓(LAMBDA (CONTENTS)␈↓
␈↓ βH␈↓↓(LABELS ((THE-CELL␈↓
␈↓ ∧@␈↓↓(LAMBDA (MSG)␈↓
␈↓ ∧p␈↓↓(IF (EQ MSG 'CONTENTS?) CONTENTS␈↓
␈↓ ¬ ␈↓↓(IF (EQ MSG 'CELL?) 'YES␈↓
␈↓ ¬P␈↓↓(IF (EQ (CAR MSG) '<-)␈↓
␈↓ ε␈↓↓(BLOCK (ASET 'CONTENTS (CADR MSG))␈↓
␈↓ εT␈↓↓THE-CELL)␈↓
␈↓ ε␈↓↓(ERROR '|UNRECOGNIZED MESSAGE - CELL|␈↓
␈↓ ε`␈↓↓MSG␈↓
␈↓ ε`␈↓↓'WRNG-TYPE-ARG)))))))␈↓
␈↓ ∧(␈↓↓THE-CELL)))␈↓

␈↓ αλThose of you who may complain about the lack of ASETQ are invited to write
␈↓ αλ(ASET' foo bar) instead of (ASET 'foo bar).

␈↓ αλEVALUATE

␈↓ αhThis is similar to the LISP function EVAL.  It evaluates its argument,
␈↓ αλand then evaluates the resulting s-expression as SCHEME code.

␈↓ αλCATCH
␈↓ αhThis is the "escape operator" which gives the user a handle on the
␈↓ αλcontrol structure of the interpreter.  The expression:

␈↓ αλ␈↓ αh␈↓↓(CATCH <identifier> <expression>)␈↓


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εr3␈↓ λ8The SCHEME Reference Manual␈↓'β␈↓'α␈↓








␈↓ αλevaluates <expression> in an environment where <identifier> is bound to a
␈↓ αλcontinuation which is "just about to return from the CATCH";  that is, if the
␈↓ αλcontinuation is called as a function of one argument, then control proceeds as
␈↓ αλif the CATCH expression had returned with the supplied (evaluated) argument as
␈↓ αλits value.  For example, consider the following obscure definition of SQRT
␈↓ αλ(Sussman's favorite style/Steele's least favorite):

␈↓ αλ␈↓ αh␈↓↓(DEFINE SQRT␈↓
␈↓ β_␈↓↓(LAMBDA (X EPSILON)␈↓
␈↓ βH␈↓↓((LAMBDA (ANS LOOPTAG)␈↓
␈↓ ∧∧␈↓↓(CATCH RETURNTAG␈↓
␈↓ ∧X␈↓↓(PROGN␈↓
␈↓ ∧d␈↓↓(ASET 'LOOPTAG (CATCH M M))␈↓ λλ;CREATE PROG TAG␈↓
␈↓ ∧d␈↓↓(IF (< (ABS (-$ (*$ ANS ANS) X)) EPSILON)␈↓
␈↓ ¬∀␈↓↓(RETURNTAG ANS)␈↓ π(␈↓ λλ;RETURN␈↓
␈↓ ¬∀␈↓↓NIL)␈↓ ¬h␈↓ εH␈↓ π(␈↓ λλ;JFCL␈↓
␈↓ ∧d␈↓↓(ASET 'ANS (//$ (+$ (//$ X ANS) ANS) 2.0))␈↓
␈↓ ∧d␈↓↓(LOOPTAG LOOPTAG))))␈↓ π(␈↓ λλ;GOTO␈↓
␈↓ βT␈↓↓1.0␈↓
␈↓ βT␈↓↓NIL)))␈↓

␈↓ αλAnyone who doesn't understand how this manages to work probably should not
␈↓ αλattempt to use CATCH.
␈↓ αhAs another example, we can define a THROW function, which may then be
␈↓ αλused with CATCH much as they are in LISP:

␈↓ αλ␈↓ αh␈↓↓(DEFINE THROW (LAMBDA (TAG RESULT) (TAG RESULT)))␈↓


␈↓ αλCREATE!PROCESS
␈↓ αhThis is the process generator for multiprocessing.  It takes one
␈↓ αλargument, an expression to be evaluated in the current environment as a
␈↓ αλseparate parallel process.  If the expression ever returns a value, the
␈↓ αλprocess automatically terminates.  The value of CREATE!PROCESS is a process id
␈↓ αλfor the newly generated process.  Note that the newly created process will not
␈↓ αλactually run until it is explicitly started.

␈↓ αλSTART!PROCESS
␈↓ αhThis takes one argument, a process id, and starts up that process.  It
␈↓ αλthen runs.

␈↓ αλSTOP!PROCESS
␈↓ αhThis also takes a process id, but stops the process.  The stopped
␈↓ αλprocess may be continued from where it was stopped by using START!PROCESS
␈↓ αλagain on it.  The magic global variable **PROCESS** always contains the
␈↓ αλprocess id of the currently running process; thus a process can stop itself by
␈↓ αλdoing (STOP!PROCESS **PROCESS**).  A stopped process is garbage collected if
␈↓ αλno live process has a pointer to its process id.

␈↓ αλEVALUATE!UNINTERRUPTIBLY


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εr4␈↓ λ8The SCHEME Reference Manual␈↓'β␈↓'α␈↓








␈↓ αhThis is the synchronization primitive.  It evaluates an expression
␈↓ αλuninterruptibly; i.e. no other process may run until the expression has
␈↓ αλreturned a value.  Note that if a funarg is returned from the scope of an
␈↓ αλEVALUATE!UNINTERRUPTIBLY, then that funarg will be uninterruptible when it is
␈↓ αλapplied; that is, the uninterruptibility property follows the rules of
␈↓ αλvariable scoping.  For example, consider the following function:

␈↓ αλ␈↓ αh␈↓↓(DEFINE SEMGEN␈↓
␈↓ β_␈↓↓(LAMBDA (SEMVAL)␈↓
␈↓ βH␈↓↓(LIST (LAMBDA ()␈↓
␈↓ ∧@␈↓↓(EVALUATE!UNINTERRUPTIBLY␈↓
␈↓ ∧p␈↓↓(ASET' SEMVAL (+ SEMVAL 1))))␈↓
␈↓ ∧⊂␈↓↓(LABELS (P (LAMBDA ()␈↓
␈↓ ¬D␈↓↓(EVALUATE!UNINTERRUPTIBLY␈↓
␈↓ ¬t␈↓↓(IF (PLUSP SEMVAL)␈↓
␈↓ ε$␈↓↓(ASET' SEMVAL (- SEMVAL 1))␈↓
␈↓ ε$␈↓↓(P)))))␈↓
␈↓ ∧p␈↓↓P))))␈↓

␈↓ αλThis returns a pair of functions which are V and P operations on a newly
␈↓ αλcreated semaphore.  The argument to SEMGEN is the initial value for the
␈↓ αλsemaphore.  Note that P busy-waits by iterating if necessary;  because
␈↓ αλEVALUATE!UNINTERRUPTIBLY uses variable-scoping rules, other processes have a
␈↓ αλchance to get in at the beginning of each iteration.  This busy-wait can be
␈↓ αλmade much more efficient by replacing the expression (P) in the definition of
␈↓ αλP with

␈↓ αλ␈↓ αh␈↓↓((LAMBDA (ME)␈↓
␈↓ βT␈↓↓(BLOCK (START!PROCESS (CREATE!PROCESS '(START!PROCESS ME)))␈↓
␈↓ ∧(␈↓↓(STOP!PROCESS ME)␈↓
␈↓ ∧(␈↓↓(P)))␈↓
␈↓ αt␈↓↓**PROCESS**)␈↓

␈↓ αλLet's see you figure this one out!  Note that a STOP!PROCESS within an
␈↓ αλEVALUATE!UNINTERRUPTIBLY forces the process to be swapped out even if it is
␈↓ αλthe current one, and so other processes get to run;  but as soon as it gets
␈↓ αλswapped in again, others are locked out as before.


␈↓ αhBesides the AINTs, SCHEME has a class of primitives known as AMACROs.
␈↓ αλThese are similar to MacLISP MACROs, in that they are expanded into equivalent
␈↓ αλcode before being executed.  Some AMACROs supplied with the SCHEME
␈↓ αλinterpreter:

␈↓ αλCOND
␈↓ αhThis is like the MacLISP COND statement, except that singleton clauses
␈↓ αλ(where the result of the predicate is the returned value) are not allowed.

␈↓ αλAND, OR
␈↓ αhThese are also as in MacLISP.


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εr5␈↓ λ8The SCHEME Reference Manual␈↓'β␈↓'α␈↓








␈↓ αλBLOCK
␈↓ αhThis is like the MacLISP PROGN, but arranges to evaluate its last
␈↓ αλargument without an extra net control frame (explained later), so that the
␈↓ αλlast argument may involved in an iteration.  Note that in SCHEME, unlike
␈↓ αλMacLISP, the body of a LAMBDA expression is ␈↓¬␈↓'β␈↓'α an implicit PROGN.

␈↓ αλDO
␈↓ αhThis is like the MacLISP "new-style" DO; old-style DO is not supported.

␈↓ αλAMAPCAR, AMAPLIST
␈↓ αhThese are like MAPCAR and MAPLIST, but they expect a SCHEME lambda
␈↓ αλclosure for the first argument.


␈↓ αλTo use SCHEME, simply incant at DDT (on MIT-AI):

␈↓ αh:LISP LIBLSP;SCHEME

␈↓ αλwhich will load up the current version of SCHEME, which will announce itself
␈↓ αλand give a prompt.  If you want to escape to LISP, merely hit ↑G.  To restart
␈↓ αλSCHEME, type (SCHEME).  Sometimes one does need to use a LISP FSUBR such as
␈↓ αλUREAD; this may be accomplished by typing, for example,

␈↓ αh␈↓↓(EVAL' (UREAD FOO BAR DSK LOSER))␈↓

␈↓ αλAfter doing this, typing ↑Q will, of course, cause SCHEME to read from the
␈↓ αλfile.

␈↓ αhThis concludes the SCHEME Reference Manual.



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εr6␈↓ λ8SCHEME Programming Examples␈↓'β␈↓'α␈↓








␈↓ αλSection 2: Some SCHEME Programming Examples



␈↓ αλTraditional Recursion

␈↓ αhHere is the good old familiar recursive definition of factorial, written
␈↓ αλin SCHEME.

␈↓ αλ␈↓ αh␈↓↓(DEFINE FACT␈↓
␈↓ β␈↓↓(LAMBDA (N) (IF (= N 0) 1␈↓
␈↓ ∧L␈↓↓(* N (FACT (- N 1)))))))␈↓

␈↓ αλWhat About Iteration?

␈↓ αhThere are many other ways to compute factorial.  One important way is
␈↓ αλthrough the use of ␈↓&iteration␈↓'β␈↓'α.  Consider the following definition of FACT.
␈↓ αλAlthough it appears to be recursive, since it "calls itself", it captures the
␈↓ αλessence of our intuitive notion of iteration, because execution of this
␈↓ αλprogram will not produce internal structures (e.g. stacks or variable
␈↓ αλbindings) which increase in size with the number of iteration steps.  This
␈↓ αλsurprising fact will be explained in two ways.
␈↓ αλ(1) We will consider programming styles in terms of substitution semantics of
␈↓ αλthe lambda calculus (Section 3).
␈↓ αλ(2) We will show how the SCHEME interpreter is implemented (Sections 4,5).

␈↓ αλ␈↓ αh␈↓↓(DEFINE FACT␈↓
␈↓ β␈↓↓(LAMBDA (N)␈↓
␈↓ β<␈↓↓(LABELS ((FACT1 (LAMBDA (M ANS)␈↓
␈↓ ¬,␈↓↓(IF (= M 0) ANS␈↓
␈↓ ε␈↓↓(FACT1 (- M 1)␈↓
␈↓ ε`␈↓↓(* M ANS))))))␈↓
␈↓ ∧(␈↓↓(FACT1 N 1))))␈↓

␈↓ αhA common iterative construct is the DO loop.  The most general form we
␈↓ αλhave seen in any programming language is the MacLISP DO [Moon].  It permits
␈↓ αλthe simultaneous initialization of any number of control variables and the
␈↓ αλsimultaneous stepping of these variables by arbitrary functions at each
␈↓ αλiteration step.  The loop is terminated by an arbitrary predicate, and an
␈↓ αλarbitrary value may be returned.  The DO loop may have a body, a series of
␈↓ αλexpressions executed for effect on each iteration.
␈↓ αhThe general form of a MacLISP DO is:

␈↓ αλ␈↓ αh␈↓↓(DO ((<var1> <init1> <step1>)␈↓
␈↓ β$␈↓↓(<var2> <init2> <step2>)␈↓
␈↓ β$␈↓↓. . .␈↓
␈↓ β$␈↓↓(<varn> <initn> <stepn>))␈↓
␈↓ β_␈↓↓(<pred> <value>)␈↓
␈↓ β_␈↓↓<body>)␈↓



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εr7␈↓ λ8SCHEME Programming Examples␈↓'β␈↓'α␈↓








␈↓ αλThe semantics of this are that the variables are bound and initialized to the
␈↓ αλvalues of the <initi> expressions, which must all be evaluated in the
␈↓ αλenvironment outside the DO; then the predicate <pred> is evaluated in the new
␈↓ αλenvironment, and if TRUE, the <value> is evaluated and returned.  Otherwise
␈↓ αλthe body is evaluated, then each of the steppers <stepi> is evaluated in the
␈↓ αλcurrent environment, all the variables made to have the results as their
␈↓ αλvalues, and the predicate evaluated again, and so on.
␈↓ αhFor example, the following MacLISP function:

␈↓ αh␈↓↓(DEFUN REV (L)␈↓
␈↓ β<␈↓↓(DO ((L1 L (CDR L1))␈↓
␈↓ βx␈↓↓(ANS NIL (CONS (CAR L1) ANS)))␈↓
␈↓ βl␈↓↓((NULL L1) ANS)))␈↓

␈↓ αλcomputes the reverse of a list.  In SCHEME, we could write the same function,
␈↓ αλin the same iterative style, as follows:

␈↓ αh␈↓↓(DEFINE REV␈↓
␈↓ β_␈↓↓(LAMBDA (L)␈↓
␈↓ βH␈↓↓(LABELS ((DOLOOP (LAMBDA (L1 ANS)␈↓
␈↓ ¬D␈↓↓(IF (NULL L1) ANS␈↓
␈↓ ¬t␈↓↓(DOLOOP (CDR L1)␈↓
␈↓ εT␈↓↓(CONS (CAR L1) ANS))))))␈↓
␈↓ ∧(␈↓↓(DOLOOP L NIL))))␈↓

␈↓ αhFrom this we can infer a general way to express iterations in SCHEME in
␈↓ αλa manner isomorphic to the MacLISP DO:

␈↓ αλ␈↓ αh␈↓↓(LABELS ((DOLOOP␈↓
␈↓ β`␈↓↓(LAMBDA (<dummy> <var1> <var2> ... <varn>)␈↓
␈↓ ∧⊂␈↓↓(IF <pred> <value>␈↓
␈↓ ∧@␈↓↓(DOLOOP <body> <step1> <step2> ... <stepn>)))))␈↓
␈↓ βH␈↓↓(DOLOOP NIL <init1> <init2> ... <initn>))␈↓

␈↓ αλThis is in fact what the supplied DO AMACRO expands into.  Note that there are
␈↓ αλno side effects in the steppings of the iteration variables.


␈↓ αλAnother Way To Do Recursion

␈↓ αhNow consider the following alternative definition of FACT.  It has an
␈↓ αλextra argument, the ␈↓&continuation␈↓'β␈↓'α [Reynolds], which is a function to call with
␈↓ αλthe answer, when we have it, rather than return a value; that is, rather than
␈↓ αλultimately reducing to the desired value, it reduces to a combination which is
␈↓ αλthe application of the continuation to the desired value.




␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εr8␈↓ λ8SCHEME Programming Examples␈↓'β␈↓'α␈↓








␈↓ αλ␈↓ αh␈↓↓(DEFINE FACT␈↓
␈↓ β␈↓↓(LAMBDA (N C)␈↓
␈↓ β0␈↓↓(IF (= N 0) (C 1)␈↓
␈↓ β`␈↓↓(FACT (- N 1)␈↓
␈↓ ∧(␈↓↓(LAMBDA (A) (C (* N A)))))))␈↓

␈↓ αλNote that we can call this like an ordinary function if we supply (LAMBDA (X)
␈↓ αλX) as the second argument.  For example, (FACT 3 (LAMBDA (X) X)) returns 6.


␈↓ αλApparently "Hairy" Control Structure

␈↓ αhA classic problem difficult to solve in most programming languages,
␈↓ αλincluding standard (stack-oriented) LISP, is the ␈↓&samefringe␈↓'β␈↓'α problem [Smith and
␈↓ αλHewitt].  The problem is to determine whether the fringes of two trees are the
␈↓ αλsame, even if the internal structures of the trees are not.  This problem is
␈↓ αλeasy to solve if one merely computes the fringe of each tree separately as a
␈↓ αλlist, and then compares the two lists.  We would like to solve the problem so
␈↓ αλthat the fringes are generated and compared incrementally.  This is important
␈↓ αλif the fringes of the trees are very large, but differ, say, in the first
␈↓ αλposition.
␈↓ αhConsider the following obscure solution to ␈↓&samefringe␈↓'β␈↓'α, which is in fact
␈↓ αλisomorphic to the one written by Shrobe and presented by Smith and Hewitt.
␈↓ αλNote that SCHEME does not have the packagers of PLASMA, and so we were forced
␈↓ αλto use continuations; rather than using packages and a ␈↓&next␈↓'β␈↓'α operator, we pass
␈↓ αλa fringe a continuation (called the "getter") which will get the next and the
␈↓ αλrest of the fringe as its two arguments.

␈↓ αλ␈↓ αh␈↓↓(DEFINE FRINGE␈↓
␈↓ β␈↓↓(LAMBDA (TREE)␈↓
␈↓ β<␈↓↓(LABELS ((FRINGEN␈↓
␈↓ ∧4␈↓↓(LAMBDA (NODE ALT)␈↓
␈↓ ∧d␈↓↓(LAMBDA (GETTER)␈↓
␈↓ ¬∀␈↓↓(IF (ATOM NODE)␈↓
␈↓ ¬D␈↓↓(GETTER NODE ALT)␈↓
␈↓ ¬D␈↓↓((FRINGEN (CAR NODE)␈↓
␈↓ ε<␈↓↓(LAMBDA (GETTER1)␈↓
␈↓ εl␈↓↓((FRINGEN (CDR NODE)␈↓
␈↓ πd␈↓↓ALT)␈↓
␈↓ εx␈↓↓GETTER1)))␈↓
␈↓ ¬P␈↓↓GETTER))))))␈↓
␈↓ ∧≤␈↓↓(FRINGEN TREE␈↓
␈↓ ¬λ␈↓↓(LAMBDA (GETTER)␈↓
␈↓ ¬8␈↓↓(GETTER '(EXHAUSTED) NIL))))))␈↓




␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εr9␈↓ λ8SCHEME Programming Examples␈↓'β␈↓'α␈↓








␈↓ αλ␈↓ αh␈↓↓(DEFINE SAMEFRINGE␈↓
␈↓ β␈↓↓(LAMBDA (TREE1 TREE2)␈↓
␈↓ β<␈↓↓(LABELS ((SAME␈↓
␈↓ ∧4␈↓↓(LAMBDA (S1 S2)␈↓
␈↓ ∧d␈↓↓(S1 (LAMBDA (X1 R1)␈↓
␈↓ ¬D␈↓↓(S2 (LAMBDA (X2 R2)␈↓
␈↓ ε$␈↓↓(IF (EQUAL X1 X2)␈↓
␈↓ εT␈↓↓(IF (EQUAL X1 '(EXHAUSTED))␈↓
␈↓ π∧␈↓↓T␈↓
␈↓ π∧␈↓↓(SAME R1 R2))␈↓
␈↓ εT␈↓↓NIL))))))))␈↓
␈↓ ∧≤␈↓↓(SAME (FRINGE TREE1)␈↓
␈↓ ∧d␈↓↓(FRINGE TREE2)))))␈↓


␈↓ αhNow let us consider an alternative solution to the ␈↓&samefringe␈↓'β␈↓'α problem.
␈↓ αλWe believe that this solution is clearer for two reasons:
␈↓ αλ(1) the implementation of SAMEFRINGE is more clearly iterative;
␈↓ αλ(2) rather than returning an object which will return both the ␈↓&first␈↓'β␈↓'α and the
␈↓ αλ␈↓&rest␈↓'β␈↓'α of a fringe to a given continuation, FRINGE returns an object which will
␈↓ αλdeliver up a component in response to a request for that component.

␈↓ αλ␈↓ αh␈↓↓(DEFINE FRINGE␈↓
␈↓ β_␈↓↓(LAMBDA (TREE)␈↓
␈↓ βH␈↓↓(LABELS ((FRINGE1␈↓
␈↓ ∧@␈↓↓(LAMBDA (NODE ALT)␈↓
␈↓ ∧d␈↓↓(IF (ATOM NODE)␈↓
␈↓ ¬∀␈↓↓(LAMBDA (MSG)␈↓
␈↓ ¬D␈↓↓(IF (EQ MSG 'FIRST) NODE␈↓
␈↓ ¬t␈↓↓(IF (EQ MSG 'NEXT) (ALT) (ERROR))))␈↓
␈↓ ¬∀␈↓↓(FRINGE1 (CAR NODE)␈↓
␈↓ ε␈↓↓(LAMBDA () (FRINGE1 (CDR NODE) ALT)))))))␈↓
␈↓ ∧(␈↓↓(FRINGE1 TREE␈↓
␈↓ ¬∀␈↓↓(LAMBDA ()␈↓
␈↓ ¬D␈↓↓(LAMBDA (MSG) (IF (EQ MSG 'FIRST) '*EOF* (ERROR))))))))␈↓

␈↓ αλ␈↓ αh␈↓↓(DEFINE SAMEFRINGE␈↓
␈↓ β_␈↓↓(LAMBDA (T1 T2)␈↓
␈↓ βH␈↓↓(DO ((C1 (FRINGE T1) (C1 'NEXT))␈↓
␈↓ ∧∧␈↓↓(C2 (FRINGE T2) (C2 'NEXT)))␈↓
␈↓ βx␈↓↓((OR (NOT (EQ (C1 'FIRST) (C2 'FIRST)))␈↓
␈↓ ∧4␈↓↓(EQ (C1 'FIRST) '*EOF*)␈↓
␈↓ ∧4␈↓↓(EQ (C2 'FIRST) '*EOF*))␈↓
␈↓ ∧∧␈↓↓(EQ (C1 'FIRST) (C2 'FIRST))))))␈↓


␈↓ αhA much simpler and more probable problem is that of building a pattern
␈↓ αλmatcher with backtracking for segment matches.  The matcher presented below is
␈↓ αλintended for matching single-level list structure patterns against lists of
␈↓ αλatoms.  A pattern is a list containing three types of elements:


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl10␈↓ λ8SCHEME Programming Examples␈↓'β␈↓'α␈↓








␈↓ αλ(1) constant atoms, which match themselves only.
␈↓ αλ(2) (THV x), which matches any single element in the expression consistently.
␈↓ αλWe may abbreviate this as ?x by means of a LISP reader macro character.
␈↓ αλ(3) (THV* x), which matches any segment of zero or more elements in the
␈↓ αλexpression consistently.  We may abbreviate this as !x.
␈↓ αλThe matcher returns either NIL, meaning no match is possible, or a list of two
␈↓ αλitems, an alist specifying the bindings of the match variables, and a
␈↓ αλcontinuation to call, if you don't like this particular set of bindings, which
␈↓ αλwill attempt to find another match.  Thus, for example, the invocation

␈↓ αλ␈↓ αh␈↓↓(MATCH '(A !B ?C ?C !B !E)␈↓
␈↓ β<␈↓↓'(A X Y Q Q X Y Z Z X Y Q Q X Y R))␈↓

␈↓ αλwould return the result

␈↓ αλ␈↓ αh␈↓↓(((E (Z Z X Y Q Q X Y R))␈↓
␈↓ β␈↓↓(C Q)␈↓
␈↓ β␈↓↓(B X Y))␈↓
␈↓ αt␈↓↓<continuation1>)␈↓

␈↓ αλwhere calling <continuation1> as a function of no arguments would produce the
␈↓ αλresult

␈↓ αλ␈↓ αh␈↓↓(((E (R))␈↓
␈↓ β␈↓↓(C Z)␈↓
␈↓ β␈↓↓(B (X Y Q Q X Y)))␈↓
␈↓ αt␈↓↓<continuation2>)␈↓

␈↓ αλwhere calling <continuation2> would produce NIL.
␈↓ αhThe MATCH function makes use of two auxiliary functions called NFIRST
␈↓ αλand NREST.  The former returns a list of the first n elements of a given list,
␈↓ αλwhile the latter returns the tail of the given list after the first n
␈↓ αλelements.

␈↓ αλ␈↓↓(DEFINE NFIRST␈↓
␈↓ α,␈↓↓(LAMBDA (E N)␈↓
␈↓ α\␈↓↓(IF (= N 0) NIL␈↓
␈↓ β␈↓↓(CONS (CAR E) (NFIRST (CDR E) (- N 1))))))␈↓

␈↓ αλ␈↓↓(DEFINE NREST␈↓
␈↓ α,␈↓↓(LAMBDA (E N)␈↓
␈↓ α\␈↓↓(IF (= N 0) E␈↓
␈↓ β␈↓↓(NREST (CDR E) (- N 1)))))␈↓

␈↓ αhThe main MATCH function also uses a subfunction called MATCH1 which
␈↓ αλtakes four arguments: the tail of the pattern yet to be matched;  the tail of
␈↓ αλthe expression yet to be matched; the alist of match bindings made so far; and
␈↓ αλa continuation to call if the match fails at this point.  A subfunction of
␈↓ αλMATCH, called MATCH*, handles the matching of segments of the expression
␈↓ αλagainst THV* match variables.  It is in the matching of segments that the


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl11␈↓ λ8SCHEME Programming Examples␈↓'β␈↓'α␈↓








␈↓ αλpotential need for backtracking enters, for segments of various lengths may
␈↓ αλhave to be tried.  After MATCH* matches a segment, it calls MATCH1 to continue
␈↓ αλthe match, giving it a failure continuation which will back up and try to
␈↓ αλmatch a longer segment if possible.  A failure can occur if a constant fails
␈↓ αλto match, or if one or the other of pattern and expression runs out before the
␈↓ αλother one does.



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl12␈↓ λ8SCHEME Programming Examples␈↓'β␈↓'α␈↓








␈↓ αλ␈↓↓(DEFINE MATCH␈↓
␈↓ α,␈↓↓(LAMBDA (PATTERN EXPRESSION)␈↓
␈↓ α\␈↓↓(LABELS ((MATCH1␈↓
␈↓ β␈↓↓(LAMBDA (P E ALIST LOSE)␈↓
␈↓ β<␈↓↓(IF (NULL P) (IF (NULL E) (LIST ALIST LOSE) (LOSE))␈↓
␈↓ βl␈↓↓(IF (ATOM (CAR P))␈↓
␈↓ ∧≤␈↓↓(IF (NULL E) (LOSE)␈↓
␈↓ ∧L␈↓↓(IF (EQ (CAR E) (CAR P))␈↓
␈↓ ∧|␈↓↓(MATCH1 (CDR P(P(CDR E) ALIST LOSE)␈↓
␈↓ ∧|␈↓↓(LOSE)))␈↓
␈↓ ∧≤␈↓↓(IF (EQ (CAAR P) 'THV)␈↓
␈↓ ∧L␈↓↓(IF (NULL E) (LOSE)␈↓
␈↓ ∧|␈↓↓((LAMBDA (V)␈↓
␈↓ ¬8␈↓↓(IF V (IF (EQ (CAR E) (CADR V))␈↓
␈↓ ε0␈↓↓(MATCH1 (CDR P) (CDR E) ALIST LOSE)␈↓
␈↓ ε0␈↓↓(LOSE))␈↓
␈↓ ¬h␈↓↓(MATCH1 (CDR P) (CDR E)␈↓
␈↓ εH␈↓↓(CONS (LIST (CADAR P) (CAR E)) ALIST)␈↓
␈↓ εH␈↓↓LOSE)))␈↓
␈↓ ¬λ␈↓↓(ASSQ (CADAR P) ALIST)))␈↓
␈↓ ∧L␈↓↓(IF (EQ (CAAR P) 'THV*)␈↓
␈↓ ∧|␈↓↓((LAMBDA (V)␈↓
␈↓ ¬8␈↓↓(IF V␈↓
␈↓ ¬h␈↓↓(IF (< (LENGTH E) (LENGTH (CADR V))) (LOSE)␈↓
␈↓ ε_␈↓↓(IF (EQUAL (NFIRST E (LENGTH (CADR V)))␈↓
␈↓ π≤␈↓↓(CADR V))␈↓
␈↓ εH␈↓↓(MATCH1 (CDR P)␈↓
␈↓ π(␈↓↓(NREST E (LENGTH (CADR V)))␈↓
␈↓ π(␈↓↓ALIST␈↓
␈↓ π(␈↓↓LOSE)␈↓
␈↓ εH␈↓↓(LOSE)))␈↓
␈↓ ¬h␈↓↓(LABELS ((MATCH*␈↓
␈↓ ε_␈↓↓(LAMBDA (N)␈↓
␈↓ εH␈↓↓(IF (> N (LENGTH E)) (LOSE)␈↓
␈↓ εx␈↓↓(MATCH1 (CDR P) (NREST E N)␈↓
␈↓ πX␈↓↓(CONS (LIST (CADAR P)␈↓
␈↓ λh␈↓↓(NFIRST E N))␈↓
␈↓ λ ␈↓↓ALIST)␈↓
␈↓ πX␈↓↓(LAMBDA ()␈↓
␈↓ λλ␈↓↓(MATCH* (+ N 1))))))))␈↓
␈↓ εH␈↓↓(MATCH* 0))))␈↓
␈↓ ¬λ␈↓↓(ASSQ (CADAR P) ALIST))␈↓
␈↓ ∧|␈↓↓(LOSE))))))))␈↓
␈↓ β<␈↓↓(MATCH1 PATTERN␈↓
␈↓ ∧≤␈↓↓EXPRESSION␈↓
␈↓ ∧≤␈↓↓NIL␈↓
␈↓ ∧≤␈↓↓(LAMBDA () NIL)))))␈↓





␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl13␈↓ λ8SCHEME Programming Examples␈↓'β␈↓'α␈↓








␈↓ αλA Useless Multiprocessing Example

␈↓ αhOne thing we might want to use multiprocessing for is to try two things
␈↓ αλin parallel, and terminate as soon as one succeeds.  We can do this with the
␈↓ αλfollowing function.

␈↓ αλ␈↓ αh␈↓↓(DEFINE TRY!TWO!THINGS!IN!PARALLEL␈↓
␈↓ β␈↓↓(LAMBDA (F1 F2)␈↓
␈↓ β0␈↓↓(CATCH C␈↓
␈↓ βT␈↓↓((LAMBDA (P1 P2)␈↓
␈↓ ∧∧␈↓↓((LAMBDA (F1 F2)␈↓
␈↓ ∧@␈↓↓(EVALUATE!UNINTERRUPTIBLY␈↓
␈↓ ∧L␈↓↓(BLOCK (ASET 'P1 (CREATE!PROCESS '(F1)))␈↓
␈↓ ¬ ␈↓↓(ASET 'P2 (CREATE!PROCESS '(F2)))␈↓
␈↓ ¬ ␈↓↓(START!PROCESS P1)␈↓
␈↓ ¬ ␈↓↓(START!PROCESS P2)␈↓
␈↓ ¬ ␈↓↓(STOP!PROCESS **PROCESS**))))␈↓
␈↓ ∧⊂␈↓↓(LAMBDA ()␈↓
␈↓ ∧4␈↓↓((LAMBDA (VALUE)␈↓
␈↓ ∧d␈↓↓(EVALUATE!UNINTERRUPTIBLY␈↓
␈↓ ∧p␈↓↓(BLOCK (STOP!PROCESS P2) (C VALUE))))␈↓
␈↓ ∧@␈↓↓(F1)))␈↓
␈↓ ∧⊂␈↓↓(LAMBDA ()␈↓
␈↓ ∧4␈↓↓((LAMBDA (VALUE)␈↓
␈↓ ∧d␈↓↓(EVALUATE!UNINTERRUPTIBLY␈↓
␈↓ ∧p␈↓↓(BLOCK (STOP!PROCESS P1) (C VALUE))))␈↓
␈↓ ∧@␈↓↓(F2)))))␈↓
␈↓ β`␈↓↓NIL NIL))))␈↓

␈↓ αλTRY!TWO!THINGS!IN!PARALLEL takes two functions of no arguments (in order to
␈↓ αλpass an unevaluated expression and its environment in for later use, so as to
␈↓ αλavoid variable conflicts).  It creates two processes to run them, and returns
␈↓ αλthe value of whichever completes first.
␈↓ αhAs an example of how to misuse TRY!TWO!THINGS!IN!PARALLEL, here is a
␈↓ αλfunction which determines the sign of an integer using only ADD1, SUB1, and
␈↓ αλEQUAL.

␈↓ αλ␈↓ αh␈↓↓(DEFINE SIGN␈↓
␈↓ β_␈↓↓(LAMBDA (N)␈↓
␈↓ βH␈↓↓(IF (EQUAL N 0) 'ZERO␈↓
␈↓ βx␈↓↓(TRY!TWO!THINGS!IN!PARALLEL␈↓
␈↓ ∧(␈↓↓(LAMBDA ()␈↓
␈↓ ∧X␈↓↓(DO ((I 0 (ADD1 I)))␈↓
␈↓ ¬λ␈↓↓((EQUAL I N) 'POSITIVE)))␈↓
␈↓ ∧(␈↓↓(LAMBDA ()␈↓
␈↓ ∧X␈↓↓(DO ((I 0 (SUB1 I)))␈↓
␈↓ ¬λ␈↓↓((EQUAL I N) 'NEGATIVE)))))))␈↓



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl14␈↓ πXSubstitution Semantics and Styles␈↓'β␈↓'α␈↓








␈↓ αλSection 3: Substitution Semantics and Programming Styles



␈↓ αhIn the previous section we showed several different SCHEME programs for
␈↓ αλcomputing the factorial function.  How are they different?  We intuitively
␈↓ αλdistinguish recursive from iterative programs, for example, by noting that
␈↓ αλrecursive programs "call themselves" but in the last section we claimed to do
␈↓ αλiteration with a seemingly recursive program.  Experienced programmers "know"
␈↓ αλthat recursion uses up "stack" so a program implemented recursively will run
␈↓ αλout of sta a sufficiently large problem.  Can we make these ideas more
␈↓ αλprecise?  One traditional approach is to model the computation with lambda
␈↓ αλcalculus.


␈↓ αλReviewing the Lambda Calculus

␈↓ αhTraditionally language constructs are broken up into two distinct
␈↓ αλclasses: imperative constructs and those with side-effects -- such as
␈↓ αλassignment and go-to; and applicative constucts -- those executed for value --
␈↓ αλsuch as arithmetic expressions.  In addition, compiled languages often require
␈↓ αλa third class, declarative constructs, but these are provided primarily to
␈↓ αλguide the compilation process and do not directly affect the semantics of
␈↓ αλexecution, and so will not concern us here.

␈↓ αhLambda calculus is a model for the applicative component of programming
␈↓ αλlanguages.  It models all non-imperative constructs as applications of
␈↓ αλfunctions and specifies the semantics of such expressions by a set of axioms
␈↓ αλor rewrite rules.  One axiom states that a combination, i.e. an expression
␈↓ αλformed by a function applied to some arguments, is equivalent to the body of
␈↓ αλthat function with the appropriate arguments substituted for the free
␈↓ αλoccurrences of the formal parameters of the function in its body:

␈↓ αλ␈↓ αh␈↓↓((LAMBDA <vars> <body>) <args>) = Subst[<args> <vars> <body>]␈↓

␈↓ αλAnother axiom requires that the meaning of an expression be independent of the
␈↓ αλnames of the formal parameters bound in the expression:

␈↓ αλ␈↓ αh␈↓↓(LAMBDA <vars> <body>)␈↓
␈↓ βH␈↓↓= (LAMBDA <newvars> Subst[<newvars> <vars> <body>])␈↓
␈↓ αh␈↓↓provided that none of <newvars> appears free in <body>.␈↓

␈↓ αλThese constraints force Subst to be defined in such a way that an important
␈↓ αλkind of ␈↓&referential transparency␈↓'β␈↓'α is obtained.  Besides these "structural"
␈↓ αλaxioms, others are provided which specify the result of certain primitive
␈↓ αλfunctions applied to specific arguments.  We shall not be concerned with these
␈↓ αλproblems here -- we will assume a small reasonable set of primitive functions.





␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl15␈↓ πXSubstitution Semantics and Styles␈↓'β␈↓'α␈↓








␈↓ αλRecursive programs

␈↓ αhNow, let's see how lambda calculus may be used (informally) to model a
␈↓ αλcomputation.  Consider the standard definition of the factorial function:

␈↓ αλ␈↓ αh␈↓↓(DEFINE FACT␈↓
␈↓ β␈↓↓(LAMBDA (N) (IF (= N 0) 1␈↓
␈↓ ∧L␈↓↓(* N (FACT (- N 1)))))))␈↓

␈↓ αλWe are being ␈↓&very␈↓'β␈↓'α informal -- lambda calculus as presented by [Church] does
␈↓ αλnot include such constucts as DEFINE, IF, or =, *, or even 1!  The "usual"
␈↓ αλlambda calculus construct for defining recursive functions is a rather obscure
␈↓ αλobject called the "fixed-point" operator.  We have been lax to avoid the
␈↓ αλhassle of "rigor mortis" in this tutorial paper.  Similarly, IF is the SCHEME
␈↓ αλconditional construct we will use for convenience, it reduces to its second or
␈↓ αλthird argument depending on whether the first reduces to TRUE or FALSE.  The
␈↓ αλobjects *, =, 0, 1, etc. may be thought of as abbreviations for complex lambda
␈↓ αλexpressions (such as Church numerals) whose details we are not interested in.
␈↓ αλOn the other hand, we may think of them as primitive expressions, defined by
␈↓ αλadditional axioms; this viewpoint leads to practical interpreter
␈↓ αλimplementations.

␈↓ αhNow let's reduce the expression (FACT 3).  We will perform the
␈↓ αλexpression reductions, except for the IF primitive, in Applicative Order (call
␈↓ αλby value), though this is not necessary, as we will discuss later.  We display
␈↓ αλa "trace" of the substitutions:

␈↓ αλ␈↓↓  =>␈↓ αh(FACT 3)␈↓
␈↓ α ␈↓↓=>␈↓ αh(IF (= 3 0) 1 (* 3 (FACT (- 3 1))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (FACT (- 3 1)))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (FACT 2))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (IF (= 2 0) 1 (* 2 (FACT (- 2 1)))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (* 2 (FACT (- 2 1))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (* 2 (FACT 1)))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (* 2 (IF (= 1 0) 1 (* 1 (FACT (- 1 1))))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (* 2 (* 1 (FACT (- 1 1)))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (* 2 (* 1 (FACT 0))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (* 2 (* 1 (IF (= 0 0) 1 (* 0 (FACT (- 0 1)))))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (* 2 (* 1 1)))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 (* 2 1))␈↓
␈↓ α ␈↓↓=>␈↓ αh(* 3 2)␈↓
␈↓ α ␈↓↓=>␈↓ αh6␈↓

␈↓ αλYou will note that we have calculated (fact 3) by a process wherein ␈↓&each␈↓'β␈↓'α
␈↓ αλ␈↓&expression is replaced␈↓'β␈↓'α by an expression which is provably equivalent to it via
␈↓ αλan axiom or which is produced by application of a primitive function.





␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl16␈↓ πXSubstitution Semantics and Styles␈↓'β␈↓'α␈↓








␈↓ αλNow, What About Iteration?

␈↓ αhConsider the "iterative" definition of FACT.  Although it appears to be
␈↓ αλrecursive, since it "calls itself", we will see that it captures the essence
␈↓ αλof our intuitive notion of iteration.

␈↓ αλ␈↓ αh␈↓↓(DEFINE FACT␈↓
␈↓ β␈↓↓(LAMBDA (N)␈↓
␈↓ β<␈↓↓(LABELS ((FACT1␈↓
␈↓ ∧4␈↓↓(LAMBDA (M ANS)␈↓
␈↓ ∧d␈↓↓(IF (= M 0) ANS␈↓
␈↓ ¬∀␈↓↓(FACT1 (- M 1) (* M ANS))))))␈↓
␈↓ βx␈↓↓(FACT1 N 1))))␈↓

␈↓ αλLet us now compute (fact 3).

␈↓ αλ␈↓↓  =>␈↓ αh(FACT 3)␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT1 3 1)␈↓
␈↓ α ␈↓↓=>␈↓ αh(IF (= 3 0) 1␈↓
␈↓ β_␈↓↓(FACT1 (- 3 1) (* 3 1)))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT1 (- 3 1) (* 3 1))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT1 2 (* 3 1))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT1 2 3)␈↓
␈↓ α ␈↓↓=>␈↓ αh(IF (= 2 0) 3␈↓
␈↓ β_␈↓↓(FACT1 (- 2 1) (* 2 3)))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT1 (- 2 1) (* 2 3))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT1 1 (* 2 3))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT1 1 6)␈↓
␈↓ α ␈↓↓=>␈↓ αh(IF (= 1 0) 6␈↓
␈↓ β_␈↓↓(FACT1 (- 1 1) (* 1 6)))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT1 (- 1 1) (* 1 6))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT1 0 (* 1 6))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT1 0 6)␈↓
␈↓ α ␈↓↓=>␈↓ αh(IF (= 0 0) 6␈↓
␈↓ β_␈↓↓(FACT1 (- 0 1) (* 0 6)))␈↓
␈↓ α ␈↓↓=>␈↓ αh6␈↓

␈↓ αλNotice that the expressions involved have a fixed maximum size independent of
␈↓ αλthe argument to FACT!  In fact, as Marvin Minsky pointed out, successive
␈↓ αλreductions produce a cycle of expressions which are identical except for the
␈↓ αλnumerical quantities involved.  Looking back, we may note by way of comparison
␈↓ αλthat the recursive version caused creation of expressions proportional in size
␈↓ αλto the argument.  This is why we think that this version of FACT is iterative
␈↓ αλrather than recursive.  At each stage of the iterative version the "state" of
␈↓ αλthe computation is summarized in two variables, the counter and the answer
␈↓ αλaccumulator, while at each stage of the recursive version the "state" contains
␈↓ αλa chain of pieces each of which contains a component of the state.  In the
␈↓ αλrecursive version of FACT, for example, the state contains the sequence of
␈↓ αλmultiplications to be performed upon return from the bottom.  It is true that
␈↓ αλthe iterative factorial also can produce expressions of arbitrary size, since


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl17␈↓ πXSubstitution Semantics and Styles␈↓'β␈↓'α␈↓








␈↓ αλthe number of bits needed to express factorial of n grows with n; but this is
␈↓ αλa property of the numbers calculated by the function which is implemented in
␈↓ αλiterative style, and not of the iterative control structure itself.  A
␈↓ αλrecursive control structure ␈↓&inherently␈↓'β␈↓'α creates expressions of unbounded size
␈↓ αλas a function of the recursion depth, while an iterative control structure
␈↓ αλproduces a cycle of equivalent expressions, and so the expressions are of
␈↓ αλapproximately the same size no matter how many iteration steps are taken.
␈↓ αλThis is the essence of the difference between the notions of iteration and
␈↓ αλrecursion.  Hewitt [MAC, p. 234] made a similar observation in passing,
␈↓ αλexpressing the difference in terms of storage used in program execution rather
␈↓ αλthan in terms of intermediate expressions produced by substitution semantics.


␈↓ αλContinuation Passing Recursion

␈↓ αhRemember the other way to compute factorials?

␈↓ αλ␈↓ αh␈↓↓(DEFINE FACT␈↓
␈↓ β␈↓↓(LAMBDA (N C)␈↓
␈↓ β0␈↓↓(IF (= N 0) (C 1)␈↓
␈↓ β`␈↓↓(FACT (- N 1)␈↓
␈↓ ∧(␈↓↓(LAMBDA (A) (C (* N A)))))))␈↓

␈↓ αλThis looks iterative on the surface! but in fact it is recursive.  Let's
␈↓ αλcompute (FACT 3 ANSWER), where ANSWER is a continuation which is to receive
␈↓ αλthe result of FACT applied to 3; that is, the last thing FACT should do is
␈↓ αλapply the continuation ANSWER to its result.

␈↓ αλ␈↓↓  =>␈↓ αh(FACT 3 ANSWER)␈↓
␈↓ α ␈↓↓=>␈↓ αh(IF (= 3 0) (ANSWER 1)␈↓
␈↓ β_␈↓↓(FACT (- 3 1) (LAMBDA (A) (ANSWER (* 3 A)))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT (- 3 1) (LAMBDA (A) (ANSWER (* 3 A))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT 2 (LAMBDA (A) (ANSWER (* 3 A))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(IF (= 2 0) ((LAMBDA (A) (ANSWER (* 3 A))) 1)␈↓
␈↓ β_␈↓↓(FACT (- 2 1)␈↓
␈↓ β`␈↓↓(LAMBDA (A)␈↓
␈↓ ∧@␈↓↓((LAMBDA (A) (ANSWER (* 3 A)))␈↓
␈↓ ∧L␈↓↓(* 2 A)))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT (- 2 1)␈↓
␈↓ β0␈↓↓(LAMBDA (A)␈↓
␈↓ ∧⊂␈↓↓((LAMBDA (A) (ANSWER (* 3 A)))␈↓
␈↓ ∧≤␈↓↓(* 2 A))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT 1␈↓
␈↓ β0␈↓↓(LAMBDA (A)␈↓
␈↓ ∧⊂␈↓↓((LAMBDA (A) (ANSWER (* 3 A)))␈↓
␈↓ ∧≤␈↓↓(* 2 A))))␈↓



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl18␈↓ πXSubstitution Semantics and Styles␈↓'β␈↓'α␈↓








␈↓ α ␈↓↓=>␈↓ αh(IF (= 1 0)␈↓
␈↓ β_␈↓↓((LAMBDA (A)␈↓
␈↓ ∧∧␈↓↓((LAMBDA (A) (ANSWER (* 3 A)))␈↓
␈↓ ∧⊂␈↓↓(* 2 A)))␈↓
␈↓ β$␈↓↓1)␈↓
␈↓ β_␈↓↓(FACT (- 1 1)␈↓
␈↓ β`␈↓↓(LAMBDA (A)␈↓
␈↓ ∧@␈↓↓((LAMBDA (A)␈↓
␈↓ ¬,␈↓↓((LAMBDA (A)␈↓
␈↓ ε_␈↓↓(ANSWER (* 3 A)))␈↓
␈↓ ¬8␈↓↓(* 2 A)))␈↓
␈↓ ∧L␈↓↓(* 1 A)))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT (- 1 1)␈↓
␈↓ β0␈↓↓(LAMBDA (A)␈↓
␈↓ ∧⊂␈↓↓((LAMBDA (A)␈↓
␈↓ ∧|␈↓↓((LAMBDA (A)␈↓
␈↓ ¬h␈↓↓(ANSWER (* 3 A)))␈↓
␈↓ ¬λ␈↓↓(* 2 A)))␈↓
␈↓ ∧≤␈↓↓(* 1 A))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(FACT 0␈↓
␈↓ β0␈↓↓(LAMBDA (A)␈↓
␈↓ ∧⊂␈↓↓((LAMBDA (A)␈↓
␈↓ ∧|␈↓↓((LAMBDA (A)␈↓
␈↓ ¬h␈↓↓(ANSWER (* 3 A)))␈↓
␈↓ ¬λ␈↓↓(* 2 A)))␈↓
␈↓ ∧≤␈↓↓(* 1 A))))␈↓
␈↓ α ␈↓↓=>␈↓ αh(IF (= 0 0)␈↓
␈↓ β_␈↓↓((LAMBDA (A)␈↓
␈↓ ∧∧␈↓↓((LAMBDA (A)␈↓
␈↓ ∧p␈↓↓((LAMBDA (A)␈↓
␈↓ ¬\␈↓↓(ANSWER (* 3 A)))␈↓
␈↓ ∧|␈↓↓(* 2 A)))␈↓
␈↓ ∧⊂␈↓↓(* 1 A)))␈↓
␈↓ β$␈↓↓1)␈↓
␈↓ β_␈↓↓(FACT (- 0 1)␈↓
␈↓ β`␈↓↓(LAMBDA (A)␈↓
␈↓ ∧@␈↓↓((LAMBDA (A)␈↓
␈↓ ¬,␈↓↓((LAMBDA (A)␈↓
␈↓ ε_␈↓↓((LAMBDA (A)␈↓
␈↓ π∧␈↓↓(ANSWER (* 3 A)))␈↓
␈↓ ε$␈↓↓(* 2 A)))␈↓
␈↓ ¬8␈↓↓(* 1 A)))␈↓
␈↓ ∧L␈↓↓(* 0 A)))))␈↓
␈↓ α ␈↓↓=>␈↓ αh((LAMBDA (A)␈↓
␈↓ βT␈↓↓((LAMBDA (A)␈↓
␈↓ ∧@␈↓↓((LAMBDA (A)␈↓
␈↓ ¬,␈↓↓(ANSWER (* 3 A)))␈↓
␈↓ ∧L␈↓↓(* 2 A)))␈↓
␈↓ β`␈↓↓(* 1 A)))␈↓
␈↓ αt␈↓↓1)␈↓


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl19␈↓ πXSubstitution Semantics and Styles␈↓'β␈↓'α␈↓








␈↓ α ␈↓↓=>␈↓ αh((LAMBDA (A)␈↓
␈↓ βT␈↓↓((LAMBDA (A)␈↓
␈↓ ∧@␈↓↓(ANSWER (* 3 A)))␈↓
␈↓ β`␈↓↓(* 2 A)))␈↓
␈↓ αt␈↓↓(* 1 1))␈↓
␈↓ α ␈↓↓=>␈↓ αh((LAMBDA (A)␈↓
␈↓ βT␈↓↓((LAMBDA (A)␈↓
␈↓ ∧@␈↓↓(ANSWER (* 3 A)))␈↓
␈↓ β`␈↓↓(* 2 A)))␈↓
␈↓ αt␈↓↓1)␈↓
␈↓ α ␈↓↓=>␈↓ αh((LAMBDA (A)␈↓
␈↓ βT␈↓↓(ANSWER (* 3 A)))␈↓
␈↓ αt␈↓↓(* 2 1))␈↓
␈↓ α ␈↓↓=>␈↓ αh((LAMBDA (A)␈↓
␈↓ βT␈↓↓(ANSWER (* 3 A)))␈↓
␈↓ αt␈↓↓2)␈↓
␈↓ α ␈↓↓=>␈↓ αh(ANSWER (* 3 2))␈↓
␈↓ α ␈↓↓=>␈↓ αh(ANSWER 6)␈↓    Whew!

␈↓ αhNote that we have computed factorial of 3 (and are about to give this
␈↓ αλresult to the continuation), but in the process no combination with FACT in
␈↓ αλthe first position has ever been reduced except as the outermost expression.
␈↓ αλIf we think of the computation in terms of evaluation rather than
␈↓ αλsubstitution, this means that ␈↓&we never returned a value from any application␈↓'β␈↓'α
␈↓ αλ␈↓&of the function FACT␈↓'β␈↓'α!  It is always possible, if we are willing to specify
␈↓ αλexplicitly what to do with the answer, to perform any calculation in this way:
␈↓ αλrather than reducing to its value, it reduces to an application of a
␈↓ αλcontinuation to its value (cf. [Fischer]).  That is, in this continuation-
␈↓ αλpassing programming style, ␈↓&a function always "returns" its result by "sending"␈↓'β␈↓'α
␈↓ αλ␈↓&it to another function␈↓'β␈↓'α.  This is the key idea.
␈↓ αhWe also note that by our previous observation, this program is
␈↓ αλessentially recursive in that the expressions produced as intermediate results
␈↓ αλof the substitution semantics grow to a size proportional to the depth.  In
␈↓ αλfact, the same information is being stored in the nested continuations
␈↓ αλproduced by this program as in the nested products produced by the traditional
␈↓ αλrecursion -- what to do with the result.
␈↓ αhOne might object that this FACT is not the same kind of object as the
␈↓ αλprevious definition, since we can't use it as a function in the same manner.
␈↓ αλNote, however, that if we supply the continuation (LAMBDA (X) X), the
␈↓ αλresulting combination (FACT 3 (LAMBDA (X) X)) will reduce to 6, just as with
␈↓ αλtraditional recursion.
␈↓ αhOne might also object that we are using function values -- the
␈↓ αλprimitives =, -, and * are functions which return values, for example.  But
␈↓ αλthis is just a property of the primitives; consider a new set of primitives
␈↓ αλ==, --, and ** which accept continuations (indeed, let == take two
␈↓ αλcontinuations: if the predicate is TRUE call the first, otherwise call the
␈↓ αλsecond).  We can then define fact as follows:




␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl20␈↓ πXSubstitution Semantics and Styles␈↓'β␈↓'α␈↓








␈↓ αλ␈↓ αh␈↓↓(DEFINE FACT␈↓
␈↓ β␈↓↓(LAMBDA (N C)␈↓
␈↓ β<␈↓↓(== N 0␈↓
␈↓ βl␈↓↓(LAMBDA () (C 1))␈↓
␈↓ βl␈↓↓(LAMBDA ()␈↓
␈↓ ∧≤␈↓↓(-- N 1␈↓
␈↓ ∧L␈↓↓(LAMBDA (M)␈↓
␈↓ ∧|␈↓↓(FACT M (LAMBDA (A) (** A N C)))))))))␈↓

␈↓ αλWe can see here that no functional application returns a value in a
␈↓ αλcomputation of factorial in this situation.  We believe that functional usage,
␈↓ αλwhere applicable (pun intended), is more perspicuous than continuation-
␈↓ αλpassing.  We shall therefore use functional primitives such as * rather than
␈↓ αλ** wherever possible, keeping in mind that we could use ** instead if we
␈↓ αλwished.



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl21␈↓ λHSome Implementation Issues␈↓'β␈↓'α␈↓








␈↓ αλSection 4: Some Implementation Issues



␈↓ αhThe key problem is ␈↓&efficiency␈↓'β␈↓'α.  Although it is easy to build an
␈↓ αλinefficient interpreter which straightforwardly performs expression
␈↓ αλsubstitutions; such an interpreter performs much unnecessary copying of
␈↓ αλintermediate expressions.  The standard solution to this problem is to use an
␈↓ αλauxiliary structure, called the ␈↓&environment␈↓'β␈↓'α, which represents a set of ␈↓&virtual␈↓'β␈↓'α
␈↓ αλ␈↓&substitutions␈↓'β␈↓'α.  Thus, when evaluating an expression of the form

␈↓ αλ␈↓ αh␈↓↓((LAMBDA <vars> <body>) <args>)␈↓   in environment␈↓↓  E␈↓

␈↓ αλinstead of reducing it by performing

␈↓ αλ␈↓ αh␈↓↓Subst[<args> <vars> <body>]␈↓

␈↓ αλwe reduce it to

␈↓ αλ␈↓ αh␈↓↓<body>   ␈↓in environment␈↓↓  E'=Pairlis[<vars> <args>* E]␈↓

␈↓ αλwhere ␈↓&pairlis␈↓'β␈↓'α creates a new environment E' in which the <vars> are logically
␈↓ αλpaired with (i.e. "bound to") the corresponding <args>* (the precise meaning
␈↓ αλof <args>* will be explained presently), and in which any variables not in
␈↓ αλ<vars> are bound as they were in E.

␈↓ αhWhen using environments, it is necessary to keep them straight.  For
␈↓ αλexample, the following expression should manage to evaluate to 7:

␈↓ αλ␈↓ αh␈↓↓(((LAMBDA (X) (LAMBDA (Y) (+ X Y))) 3) 4)␈↓

␈↓ αλA substitution interpreter would cause the free occurrence of x in the inner
␈↓ αλlambda expression to be replaced by 3 before applying that lambda expression
␈↓ αλto 4.  An interpreter which uses environments must arrange for the expression
␈↓ αλ(+ x y) to be evaluated in an environment such that x is bound to 3 and y is
␈↓ αλbound to 4.  This implies that when the inner lambda expression is applied to
␈↓ αλ4, there must be associated with it an environment in which x is bound to 3.
␈↓ αλIn order to solve this problem we introduce the notion of a ␈↓&closure␈↓'β␈↓'α [McCarthy]
␈↓ αλ[Moses] which is a data structure containing a lambda expression, and an
␈↓ αλenvironment to be used when that lambda expression is applied to arguments.
␈↓ αλWe will notate a closure using the ␈↓&beta␈↓'β␈↓'α construct (our own notation, but
␈↓ αλisomorphic to the LISP ␈↓&funarg␈↓'β␈↓'α construct) as follows:

␈↓ αλ␈↓ αh␈↓↓(BETA (LAMBDA <vars> <body>) <environment>)␈↓

␈↓ αλWhen a lambda expression is to be evaluated, because it was passed as an
␈↓ αλargument, it evaluates to a closure of that lambda expression in the
␈↓ αλenvironment it is evaluated in (i.e., the environment it was passed from):

␈↓ αλ␈↓ αh␈↓↓(LAMBDA <vars> <body>)   ␈↓in environment␈↓↓  E␈↓


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl22␈↓ λHSome Implementation Issues␈↓'β␈↓'α␈↓








␈↓ αλevaluates to

␈↓ αλ␈↓ αh␈↓↓(BETA (LAMBDA <vars> <body>) E)   ␈↓in environment␈↓↓  E␈↓

␈↓ αλWhen a closure is to be applied to some arguments:

␈↓ αλ␈↓ αh␈↓↓((BETA (LAMBDA <vars> <body>) E1) <args>)   ␈↓in environment␈↓↓  E2␈↓

␈↓ αλthis is performed by reducing the application expression to

␈↓ αλ␈↓ αh␈↓↓<body>   ␈↓in environment␈↓↓  Pairlis[<vars> <args in E2> E1]␈↓

␈↓ αλThat is, any free variables in the closed lambda expression refer to the
␈↓ αλenvironment as of the time of closure (E1), not as of the time of application
␈↓ αλ(E2), whereas the arguments are evaluated in the application environment as
␈↓ αλexpected.
␈↓ αhThis notion of ␈↓&closure␈↓'β␈↓'α has gone by many other names in other contexts.
␈↓ αλIn LISP, for example, such a closure has been traditionally known as a ␈↓&funarg␈↓'β␈↓'α.
␈↓ αλALGOL has several related ideas.  Every ALGOL procedure is, at the time of its
␈↓ αλinvocation, essentially a "downward funarg".  In addition, expressions which
␈↓ αλare passed by name instead of by value are closed through the use of
␈↓ αλmechanisms called ␈↓&thunks␈↓'β␈↓'α [Ingerman].  It turns out that an ␈↓&actor␈↓'β␈↓'α (other than a
␈↓ αλcell or a serializer) is also a closure.  Hewitt [Smith and Hewitt] describes
␈↓ αλan actor as consisting of a ␈↓&script␈↓'β␈↓'α, which is code to be executed, and a ␈↓&set of␈↓'β␈↓'α
␈↓ αλ␈↓&acquaintances␈↓'β␈↓'α, which are other actors which it knows about.  We contend that
␈↓ αλthe script is in fact identical to the lambda expression in a closure, and
␈↓ αλthat the set of acquaintances is in effect an environment.  As an example,
␈↓ αλconsider the following code for ␈↓&cons␈↓'β␈↓'α taken from [Smith and Hewitt] (cf.
␈↓ αλ[Fischer]):

␈↓ αλ␈↓↓[CONS ≡␈↓
␈↓ α8␈↓↓(≡> [=A =B]␈↓
␈↓ αh␈↓↓(CASES␈↓
␈↓ β␈↓↓(≡> FIRST?␈↓
␈↓ β<␈↓↓A)␈↓
␈↓ β␈↓↓(≡> REST?␈↓
␈↓ β<␈↓↓B)␈↓
␈↓ β␈↓↓(≡> LIST?␈↓
␈↓ β<␈↓↓YES)))]␈↓

␈↓ αλWhen the form (cons x y) is evaluated, the result is an (evaluated) ␈↓&cases␈↓'β␈↓'α
␈↓ αλstatement, which is a receiver ready to accept a message such as "first?" or
␈↓ αλ"rest?".  This resulting receiver evidently ␈↓&knows about␈↓'β␈↓'α the actors x and y as
␈↓ αλbeing bound to the variables a and b; it is evidently a ␈↓&closure␈↓'β␈↓'α of the cases
␈↓ αλscript plus a set of acquaintances which includes x and y (as well as "first?"
␈↓ αλand "rest?" and "yes", for example; PLASMA considers such "constant
␈↓ αλacquaintances" to be part of the set, whereas in SCHEME we might prefer to
␈↓ αλconsider them part of the script).  Once we realize that it is a closure and
␈↓ αλnothing more, we can see easily how to express the same semantics in SCHEME:



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl23␈↓ λHSome Implementation Issues␈↓'β␈↓'α␈↓








␈↓ αλ␈↓↓(DEFINE CONS␈↓
␈↓ α,␈↓↓(LAMBDA (A B)␈↓
␈↓ α\␈↓↓(LAMBDA (M)␈↓
␈↓ β␈↓↓(IF (EQ M 'FIRST?) A␈↓
␈↓ β<␈↓↓(IF (EQ M 'REST?) B␈↓
␈↓ βl␈↓↓(IF (EQ M 'LIST?) 'YES␈↓
␈↓ ∧≤␈↓↓(ERROR '|UNRECOGNIZED MESSAGE - CONS|␈↓
␈↓ ∧|␈↓↓M␈↓
␈↓ ∧|␈↓↓'WRNG-TYPE-ARG)))))))␈↓

␈↓ αλNote that we have used explicit ␈↓&eq␈↓'β␈↓'α tests on the incoming message rather than
␈↓ αλthe implicit pattern-matching of the ␈↓&cases␈↓'β␈↓'α statement, but the underlying
␈↓ αλsemantics of the approach are the same.
␈↓ αhThere are several important consequences of closing every lambda
␈↓ αλexpression in the environment from which it is passed (i.e., in its "lexical"
␈↓ αλor "static" environment).  First, the axioms of lambda calculus are
␈↓ αλautomatically preserved.  Thus, referential transparency is enforced.  This in
␈↓ αλturn implies that there are no "fluid" variable bindings (as there are in
␈↓ αλstandard stack implementations of LISP such as MacLISP).  Second, the upward
␈↓ αλfunarg problem [Moses] requires that the environment structure be potentially
␈↓ αλtree-like.  Finally, the environment at any point in a computation can never
␈↓ αλbe deeper than the lexical depth of the expression being evaluated at that
␈↓ αλtime; i.e., the environment contains bindings only for variables bound in
␈↓ αλlambdas lexically surrounding the expression being evaluated.  This is true
␈↓ αλ␈↓&even if recursive functions are involved␈↓'β␈↓'α.  It follows that if list structures
␈↓ αλare used to implement environments, the time to look up a variable is
␈↓ αλproportional only to the lexical distance from the reference to the binding
␈↓ αλand not to the depth of recursion or any other dynamic parameter.  Therefore
␈↓ αλit is not necessarily as expensive as many people have been led to believe.
␈↓ αλFurthermore, it is not even necessary to scan the environment for the
␈↓ αλvariable, since its value must be in a known position relative to the top of
␈↓ αλthe environment structure;  this position can be computed by a compiler at
␈↓ αλcompile time on the basis of lexical scope.  The tree-like structure of an
␈↓ αλenvironment prevents one from merely indexing into the it, however; it is
␈↓ αλnecessary to ␈↓&cdr␈↓'β␈↓'α down it.  (Some ALGOL compilers use a similar technique
␈↓ αλinvolving base registers pointing to sets of variables for each level of block
␈↓ αλnesting; it is necessary to determine the base pointer for the block desired
␈↓ αλfor a variable reference, but then the variable is at a known offset from the
␈↓ αλbase address.) It also follows that an iterative programming style will lead
␈↓ αλto no net accumulation of environment structures in the interpreter.  The
␈↓ αλrecursive style, with or without continuation-passing, ␈↓&will␈↓'β␈↓'α lead to
␈↓ αλaccumulation of environment structures as a function of the recursion depth,
␈↓ αλnot because any environment becomes arbitrarily deep, but rather because at
␈↓ αλeach level of recursion it is necessary to save the environment at that point.
␈↓ αλIt is saved by the interpreter in the case of traditional recursion, so that
␈↓ αλcomputation can continue in the correct environment on return from the
␈↓ αλrecursive call;  it is saved as part of the continuation closure in
␈↓ αλcontinuation-passing.

␈↓ αhAnother problem is concerned with control.  This is a consequence of the


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl24␈↓ λHSome Implementation Issues␈↓'β␈↓'α␈↓








␈↓ αλ␈↓&functional interpretation␈↓'β␈↓'α of the lambda calculus, i.e. the view that a
␈↓ αλ"expression" (combination) represents a value to be "returned" (to replace the
␈↓ αλcombination) to its "caller" (the process evaluating the combination
␈↓ αλcontaining the original one).  The interpreter must provide for correctly
␈↓ αλresuming the caller when the callee has returned its value.  The state of the
␈↓ αλcomputation at the time of the call must therefore be preserved.  We see,
␈↓ αλthen, that part of the state of the computation must be (a pointer to) the
␈↓ αλpreserved state of its caller;  we will call this component of the state the
␈↓ αλ␈↓&clink␈↓'β␈↓'α [McDermott and Sussman] [Bobrow and Wegbreit].  Just before the
␈↓ αλevaluation of a subexpression, the state of the current computation, including
␈↓ αλthe ␈↓&clink␈↓'β␈↓'α, must be gathered together into a single data structure, which we
␈↓ αλwill call a ␈↓&frame␈↓'β␈↓'α;  the ␈↓&clink␈↓'β␈↓'α is then altered to point to this new frame.  The
␈↓ αλevaluation of the subexpression then returns by restoring the state of the
␈↓ αλprocess from the current ␈↓&clink␈↓'β␈↓'α.  Note that the value of the subexpression had
␈↓ αλbetter not be part of the state, for otherwise it would be lost by the state
␈↓ αλrestoration.  Thus, we only build a new frame if further computation would
␈↓ αλresult in losing information which might be necessary.  This only occurs if we
␈↓ αλmust somehow return to that state.  This in turn can only occur if we must
␈↓ αλevaluate an expression whose value must be obtained in order to continue
␈↓ αλcomputation in the current state.
␈↓ αhThis implies that no frame need be created in order to ␈↓&apply␈↓'β␈↓'α a lambda
␈↓ αλexpression to its arguments.  This in turn implies that the iterative and
␈↓ αλcontinuation-passing styles lead to ␈↓&no net creation of frames␈↓'β␈↓'α, because they
␈↓ αλare implemented ␈↓&only␈↓'β␈↓'α in terms of explicit lambda applications, whereas the
␈↓ αλrecursive style leads to the creation of one net frame per level of recursive
␈↓ αλdepth, because the recursive invocation involves the evaluation of a
␈↓ αλexpression containing the recursive lambda application as a subexpression.
␈↓ αhA clink in a lambda calculus-based interpreter is in fact equivalent to
␈↓ αλa low-level default continuation as created by the PLASMA interpreter.  Such a
␈↓ αλcontinuation is a (closed) lambda expression of one argument whose script will
␈↓ αλcarry on the computation after receiving the value of the subexpression.  The
␈↓ αλclink mechanism is therefore not necessary, if we are willing to transform all
␈↓ αλour programs into pure continuation-passing style.  We could do this
␈↓ αλexplicitly, by requiring the user to write his programs in this form; or
␈↓ αλimplicitly, as PLASMA does, by creating these one-argument continuations as
␈↓ αλnecessary, passing them as hidden extra arguments to lambda expressions which
␈↓ αλbehave like functions.  On the other hand, we may think of a clink as a highly
␈↓ αλoptimized continuation, whose "script" is that carefully coded portion of the
␈↓ αλlambda calculus interpreter which restores the frame and then carries on.  We
␈↓ αλfind this notion useful in defining a primitive, CATCH (named for the CATCH
␈↓ αλconstruct in MacLISP [Moon]), for "hairy control structure", similar to
␈↓ αλReynolds' ESCAPE operator [Reynolds], which makes these low-level
␈↓ αλcontinuations available to the user.  Note that PLASMA has a similar facility
␈↓ αλfor getting hold of the low-level continuations, namely the "␈↓↓≡≡>␈↓" receiver
␈↓ αλconstruct.

␈↓ αhAnother problem for the implementor of an interpreter of a lambda
␈↓ αλcalculus based language is the order in which to perform reductions.  There
␈↓ αλare two standard orders of evaluation (and several other semi-standard ones,
␈↓ αλwhich we will not consider here).  The first is ␈↓&Normal Order␈↓'β␈↓'α, which


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl25␈↓ λHSome Implementation Issues␈↓'β␈↓'α␈↓








␈↓ αλcorresponds roughly to ALGOL's "call by name", and the second is ␈↓&Applicative␈↓'β␈↓'α
␈↓ αλ␈↓&Order␈↓'β␈↓'α, which corresponds roughly to ALGOL's "call by value" or to LISP
␈↓ αλfunctional application.
␈↓ αhUnder a call-by-name implementation, the <args>* mentioned above are in
␈↓ αλfact the actual argument expressions, each paired with the environment E.  The
␈↓ αλevaluator has two additional rules:
␈↓ αλ(1) when a variable x is to be evaluated in environment E1, then its
␈↓ αλassociated expression-environment pair [A,E2] (which is equivalent to an ALGOL
␈↓ αλthunk) is looked up in E1, and then A is evaluated in E2.
␈↓ αλ(2) when a "primitive operator" is to be applied, its arguments must be
␈↓ αλevaluated at that time, and then the operator applied in a call-by-value
␈↓ αλmanner.
␈↓ αhUnder a call-by-value implementation, the <args>* are the ␈↓&values␈↓'β␈↓'α of the
␈↓ αλargument expressions; i.e., the argument expressions are evaluated in
␈↓ αλenvironment E, and only then is the lambda expression applied.  Note that this
␈↓ αλleads to trouble in defining conditionals.  Under call-by-name one may define
␈↓ αλpredicates to return (LAMBDA (X Y) X) for TRUE and (LAMBDA (X Y) Y) for FALSE,
␈↓ αλand then one may simply write

␈↓ αλ␈↓ αh␈↓↓((= A B) <do this if TRUE> <do this if FALSE>)␈↓

␈↓ αλThis trick depends implicitly on the order of evaluation.  It will not work
␈↓ αλunder call-by-value, nor in general under any other reductive order except
␈↓ αλNormal Order.  It is therefore necessary to introduce a special primitive
␈↓ αλoperator (such as "if") which is applied in a ␈↓&call-by-name␈↓'β␈↓'α manner.  This leads
␈↓ αλus to the interesting conclusion that a practical lambda calculus interpreter
␈↓ αλcannot be ␈↓&purely␈↓'β␈↓'α call-by-name ␈↓&or␈↓'β␈↓'α call-by-value;  it is necessary to have at
␈↓ αλleast a little of each.
␈↓ αhThere is a fundamental problem, however, with using Normal Order
␈↓ αλevaluation in a lambda calculus interpreter, which is brought out by the
␈↓ αλiterative programming style.  We already know that no net frames are created
␈↓ αλby iterative programs, and that no net environment structures are created
␈↓ αλeither.  The problem is that under a call-by-name implementation there may be
␈↓ αλa net ␈↓&thunk␈↓'β␈↓'α structure created proportional in size to the number of iteration
␈↓ αλsteps.  This problem is inherent in Normal Order, because Normal Order
␈↓ αλsubstitution semantics exhibit the same phenomenon of increasing expression
␈↓ αλsize.  Therefore iteration cannot be effectively modeled in a call-by-name
␈↓ αλinterpreter.  An alternative view is that a call-by-name interpreter remembers
␈↓ αλmore than is logically necessary to perform the computations indicated by the
␈↓ αλoriginal expressions.  This is indicated by the fact that the Applicative
␈↓ αλOrder substitution semantics lead to expressions of fixed maximum size
␈↓ αλindependent of the number of iteration steps.
␈↓ αhIt turns out that this conflict between call-by-name and iteration is
␈↓ αλresolved by the use of continuation-passing.  If we use a pure continuation-
␈↓ αλpassing programming style, then Normal Order and Applicative Order are the
␈↓ αλsame order!  In pure continuation-passing no combination is ever a
␈↓ αλsubcombination of another combination.  (This is the justification for the
␈↓ αλfact mentioned above that no clinks are needed if pure continuation-passing
␈↓ αλstyle is used.) Thus, if we wish to model iteration in pure lambda calculus
␈↓ αλwithout even an ␈↓&if␈↓'β␈↓'α primitive, we can use Normal Order substitutions and


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl26␈↓ λHSome Implementation Issues␈↓'β␈↓'α␈↓








␈↓ αλexpress the iteration in the continuation-passing style.
␈↓ αhUnder ␈↓&any␈↓'β␈↓'α reductive order, whether Normal Order, Applicative Order, or
␈↓ αλany other order, it is in practice convenient to introduce a means of
␈↓ αλterminating the evaluation process on a given form; in order to do this we
␈↓ αλintroduce three different and equally useful notions.  The first is the
␈↓ αλ␈↓&primitive operator␈↓'β␈↓'α such as +; the evaluator can apply such an operator
␈↓ αλdirectly, without substituting a lambda expression for the operator and
␈↓ αλreducing the resulting form.  The second is the ␈↓&self-evaluating constant␈↓'β␈↓'α; this
␈↓ αλis used for primitive objects such as numbers, which effectively behave as if
␈↓ αλalways "bound to themselves" in any environment.  The third is the ␈↓"ing␈↓'β␈↓'α
␈↓ αλ␈↓&function␈↓'β␈↓'α, which protects its argument from reductions so that it is returned
␈↓ αλas is; this is used for treating forms as data in the usual LISP manner.
␈↓ αhThese three ideas are not logically necessary, since the evaluation
␈↓ αλprocess will (eventually) terminate when no reductions can be made, but they
␈↓ αλare a great convenience for introducing various functions and data into the
␈↓ αλlambda calculus.  Note too that some are easily defined in terms of the
␈↓ αλothers;  for example, instead of letting 3 be a self-evaluating constant, we
␈↓ αλcould let 3 be a primitive operator of no arguments which returned 3, or we
␈↓ αλcould merely quote it; similarly, instead of quoting forms we could let forms
␈↓ αλbe a self-evaluating data type, as in MDL [Galley and Pfister] (better known
␈↓ αλas MUDDLE), written with different parentheses.  Because, as we have said,
␈↓ αλthese constructs are all strictly for convenience, we will not strive for any
␈↓ αλkind of minimality, but will continue to use all three notions in our
␈↓ αλinterpreter, as we already have in our examples.  We provide an interface so
␈↓ αλthat all MacLISP subrs may be used as primitive operators;  we define numbers
␈↓ αλto be self-evaluating; and we will use QUOTE to quote forms as in LISP (and
␈↓ αλthus we may use the "'" character as an abbreviation).

␈↓ αhOne final issue which the implementor of a lambda calculus based
␈↓ αλinterpreter should consider is that of extensions to the language, such as
␈↓ αλprimitives for side effects, multiprocessing, and synchronization of
␈↓ αλprocesses.  Note that these are ideas which are very hard, if not impossible,
␈↓ αλto model using the substitution semantics of the lambda calculus, but which
␈↓ αλare easily incorporated in other semantic models, including the environment
␈↓ αλinterpreter and, perhaps more notably, the ACTORS model [Greif and Hewitt].
␈↓ αλThe fundamental problem with modelling such concepts using substitution
␈↓ αλsemantics is that substitution produces ␈↓&copies␈↓'β␈↓'α of expressions, and so cannot
␈↓ αλmodel the notion of ␈↓&sharing␈↓'β␈↓'α very well.  In an interpreter which uses
␈↓ αλenvironments, all instances of a variable scoped in a given environment refer
␈↓ αλto the same virtual substitution contained in that environment, and so may be
␈↓ αλthought of as sharing a ␈↓&value cell␈↓'β␈↓'α in that environment.  We can take advantage
␈↓ αλof this sharing by introducing a primitive operator which modifies the
␈↓ αλcontents of a value cell; since all occurrences refer to the same value cell,
␈↓ αλchanging the contents of that value cell will change the result of future
␈↓ αλreferences to that value cell (i.e., occurrences of the variable which invoke
␈↓ αλthe virtual substitution mechanism).  Such a primitive operator would then be
␈↓ αλsimilar to the SET function of LISP, or the := of ALGOL.  We include such an
␈↓ αλoperator, ASET, in our interpreter.
␈↓ αhIntroducing multiprocessing into the interpreter is fairly
␈↓ αλstraightforward; all that is necessary is to introduce a mechanism for time-


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl27␈↓ λHSome Implementation Issues␈↓'β␈↓'α␈↓








␈↓ αλslicing the interpreter among several processes.  One can even model this in
␈↓ αλsubstitution semantics by supposing that there can be more than one
␈↓ αλexpression, and at each step an expression is randomly chosen to perform a
␈↓ αλreduction within.  (On the other hand, ␈↓&synchronizing␈↓'β␈↓'α of the processes is very
␈↓ αλhard to model using substitution semantics!)
␈↓ αhSince our value cells effectively solve the readers and writers problem
␈↓ αλ(i.e. reads and writes of variables are indivisible) no more than our side
␈↓ αλeffect primitive is necessary to synchronize our processes [Dijkstra] [Knuth]
␈↓ αλ[Lamport].  However, the techniques for achieving synchronization using only
␈↓ αλ:= are quite cumbersome and opaque.  It behooves the implementor to make
␈↓ αλthings easier for the user by introducing a more tractable synchronization
␈↓ αλprimitive (e.g. P+V or monitors or path expressions or ...).  Machine language
␈↓ αλprogrammers have long known that the easiest way to synchronize processes is
␈↓ αλto turn off the scheduling clock during the execution of critical code.  We
␈↓ αλhave introduced such a primitive, EVALUATE!UNINTERRUPTIBLY, (which is a sort
␈↓ αλof "over-anxious serializer", because it locks out the whole world) into our
␈↓ αλinterpreter.



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl28␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλSection 5: The Implementation of the Interpreter



␈↓ αhHere we present a real live SCHEME interpreter.  This particular version
␈↓ αλwas written primarily for expository purposes;  it works, but not as
␈↓ αλefficiently as possible.  The "production version" of SCHEME is coded somewhat
␈↓ αλmore intricately, and runs about twice as fast as the interpreter presented
␈↓ αλbelow.
␈↓ αhThe basic idea behind the implementation is ␈↓&think machine language␈↓'β␈↓'α.  In
␈↓ αλparticular, we must not use recursion in the implementation language to
␈↓ αλimplement recursion in the language being interpreted.  This is a crucial
␈↓ αλmistake which has screwed many language implementations (e.g. Micro-PLANNER
␈↓ αλ[Sussman]).  The reason for this is that if the implementation language does
␈↓ αλnot support certain kinds of control structures, then we will not be able to
␈↓ αλeffectively interpret them.  Thus, for example, if the control frame structure
␈↓ αλin the implementation language is constrained to be stack-like, then modelling
␈↓ αλmore general control structures in the interpreted language will be very
␈↓ αλdifficult unless we divorce ourselves from the constrained structures at the
␈↓ αλoutset.
␈↓ αhIt will be convenient to think of an implementation machine which has
␈↓ αλcertain operations, which are "micro-coded" in LISP;  these are used to
␈↓ αλoperate on various "registers", which are represented as free LISP variables.
␈↓ αλThese registers are:

␈↓ αλ**EXP**
␈↓ αhThe expression currently being evaluated.

␈↓ αλ**ENV**
␈↓ αhA pointer to the environment in which to evaluate EXP.

␈↓ αλ**CLINK**
␈↓ αhA pointer to the frame for the computation of which the current one is a
␈↓ αλsubcomputation.

␈↓ αλ**PC**
␈↓ αhThe "program counter".  As each "instruction" is executed, it updates
␈↓ αλ**PC** to point to the next instruction to be executed.

␈↓ αλ**VAL**
␈↓ αhThe returned value of a subcomputation.  This register is ␈↓¬␈↓'β␈↓'α saved and
␈↓ αλrestored in **CLINK** frames; in fact, its sole purpose is to pass values back
␈↓ αλsafely across the restoration of a frame.

␈↓ αλ**UNEVLIS**, **EVLIS**
␈↓ αhThese are utility registers which are part of the state of the
␈↓ αλinterpreter (they are saved in **CLINK** frames).  They are used primarily for
␈↓ αλevaluation of components of combinations, but may be used for other purposes
␈↓ αλalso.



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl29␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλ**TEM**
␈↓ αhA super-temporary register, used for random purposes, and not saved in
␈↓ αλ**CLINK** frames or across interrupts.  It therefore may not be used to pass
␈↓ αλinformation between "instructions" of the "machine", and so is best thought of
␈↓ αλas an internal hardware register.

␈↓ αλ**QUEUE**
␈↓ αhA list of all processes other than the one currently being interpreted.

␈↓ αλ**TICK**
␈↓ αhA magic register which a "hardware clock" sets to T every so often, used
␈↓ αλto drive the scheduler.

␈↓ αλ**PROCESS**
␈↓ αhThis register always contains the name of the process currently swapped
␈↓ αλin and running.



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl30␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αhThe following declarations and macros are present only to make the
␈↓ αλcompiler happy, and to make the version number of the SCHEME implementation
␈↓ αλavailable in the global variable VERSION.

␈↓ αλ␈↓↓(DECLARE (SPECIAL **EXP** **UNEVLIS** **ENV** **EVLIS** **PC** **CLINK** **VAL** **TEM**␈↓
␈↓ ∧∧␈↓↓**TOP** **QUEUE** **TICK** **PROCESS** **QUANTUM**␈↓
␈↓ ∧∧␈↓↓VERSION LISPVERSION))␈↓

␈↓ αλ␈↓↓(DEFUN VERSION MACRO (X)␈↓
␈↓ α\␈↓↓(COND (COMPILER-STATE (LIST 'QUOTE (STATUS UREAD)))␈↓
␈↓ β$␈↓↓(T (RPLACA X 'QUOTE)␈↓
␈↓ βH␈↓↓(RPLACD X (LIST VERSION))␈↓
␈↓ βH␈↓↓(LIST 'QUOTE VERSION))))␈↓

␈↓ αλ␈↓↓(DECLARE (READ))␈↓

␈↓ αλ␈↓↓(SETQ VERSION ((LAMBDA (COMPILER-STATE) (VERSION)) T))␈↓


␈↓ αhThe function SCHEME initializes the system driver.  The two SETQ's
␈↓ αλmerely set up version numbers.  The top level loop itself is written in
␈↓ αλSCHEME, and is a LABELS which binds the function **TOP** to be a read-eval-
␈↓ αλprint loop.  The LISP global variable **TOP** is initialized to the closure of
␈↓ αλthe **TOP** function for convenience and accessibility to user-defined
␈↓ αλfunctions.

␈↓ αλ␈↓↓(DEFUN SCHEME ()␈↓
␈↓ α\␈↓↓(SETQ VERSION (VERSION)  LISPVERSION (STATUS LISPVERSION))␈↓
␈↓ α\␈↓↓(TERPRI)␈↓
␈↓ α\␈↓↓(PRINC '|This is SCHEME |)␈↓
␈↓ α\␈↓↓(PRINC VERSION)␈↓
␈↓ α\␈↓↓(PRINC '| running in LISP |)␈↓
␈↓ α\␈↓↓(PRINC LISPVERSION)␈↓
␈↓ α\␈↓↓(SETQ **ENV** NIL  **QUEUE** NIL␈↓
␈↓ β$␈↓↓**PROCESS** (CREATE!PROCESS '(**TOP** '|SCHEME -- Toplevel|)))␈↓
␈↓ α\␈↓↓(SWAPINPROCESS)␈↓
␈↓ α\␈↓↓(ALARMCLOCK 'RUNTIME **QUANTUM**)␈↓
␈↓ α\␈↓↓(MLOOP))␈↓

␈↓ αλ␈↓↓(SETQ **TOP**␈↓
␈↓ αP␈↓↓'(BETA (LAMBDA (**MESSAGE**)␈↓
␈↓ βH␈↓↓(LABELS ((**TOP1**␈↓
␈↓ ∧@␈↓↓(LAMBDA (**IGNORE1** **IGNORE2** **IGNORE3**)␈↓
␈↓ ∧d␈↓↓(**TOP1** (TERPRI) (PRINC '|==> |)␈↓
␈↓ ¬\␈↓↓(PRINT (SET '* (EVALUATE (READ))))))))␈↓
␈↓ βx␈↓↓(**TOP1** (TERPRI) (PRINC **MESSAGE**) NIL)))␈↓
␈↓ β$␈↓↓NIL))␈↓

␈↓ αhWhen the LISP alarmclock tick occurs, the global register **TICK** is
␈↓ αλset to T.  **QUANTUM**, the amount of runtime between ticks, is measured in


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl31␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλmicro-seconds.

␈↓ αλ␈↓↓(DEFUN SETTICK (X) (SETQ **TICK** T))␈↓

␈↓ αλ␈↓↓(SETQ **QUANTUM** 1000000.  ALARMCLOCK 'SETTICK)␈↓

␈↓ αhMLOOP is the main loop of the interpreter.  It may be thought of as the
␈↓ αλinstruction dispatch in the micro-code of the implementation machine.  If an
␈↓ αλalarmclock tick has occurred, and interrupts are allowed, then the scheduler
␈↓ αλis called to switch processes.  Otherwise the "instruction" specified by
␈↓ αλ**PC** is executed via FASTCALL.

␈↓ αλ␈↓↓(DEFUN MLOOP ()␈↓
␈↓ α\␈↓↓(DO ((**TICK** NIL)) (NIL)␈↓ ¬h;DO forever␈↓
␈↓ β␈↓↓(AND **TICK** (ALLOW) (SCHEDULE))␈↓
␈↓ β␈↓↓(FASTCALL **PC**)))␈↓

␈↓ αhFASTCALL is essentially a FUNCALL optimized for compiled "microcode".
␈↓ αλNote the way it pulls the SUBR property to the front of the property list if
␈↓ αλpossible for speed.

␈↓ αλ␈↓↓(DEFUN FASTCALL (ATSYM)␈↓
␈↓ α\␈↓↓(COND ((EQ (CAR (CDR ATSYM)) 'SUBR)␈↓
␈↓ β0␈↓↓(SUBRCALL NIL (CADR (CDR ATSYM))))␈↓
␈↓ β$␈↓↓(T ((LAMBDA (SUBR)␈↓
␈↓ ∧4␈↓↓(COND (SUBR (REMPROP ATSYM 'SUBR)␈↓
␈↓ ¬D␈↓↓(PUTPROP ATSYM SUBR 'SUBR)␈↓
␈↓ ¬D␈↓↓(SUBRCALL NIL SUBR))␈↓
␈↓ ∧|␈↓↓(T (FUNCALL ATSYM))))␈↓
␈↓ βT␈↓↓(GET ATSYM 'SUBR)))))␈↓

␈↓ αhInterrupts are allowed unless the variable *ALLOW* is bound to NIL in
␈↓ αλthe current environment.  This is used to implement the
␈↓ αλEVALUATE!UNINTERRUPTIBLY primitive.

␈↓ αλ␈↓↓(DEFUN ALLOW ()␈↓
␈↓ α\␈↓↓((LAMBDA (VCELL)␈↓
␈↓ βH␈↓↓(COND (VCELL (CADR VCELL))␈↓
␈↓ ∧⊂␈↓↓(T T)))␈↓
␈↓ αh␈↓↓(ASSQ '*ALLOW* **ENV**)))␈↓

␈↓ αhNext comes the scheduler.  It is apparently interrupt-driven, but in
␈↓ αλfact is not.  The key here is to ␈↓&think microcode␈↓'β␈↓'α!  There is one place in the
␈↓ αλmicrocoded instruction interpretation loop which checks to see if there is an
␈↓ αλinterrupt pending; in our "machine", this occurs in MLOOP, where **TICK** is
␈↓ αλchecked on every cycle.  This is another case where we must beware of using
␈↓ αλtoo much of the power of the host language; just as we must avoid using host
␈↓ αλrecursion directly to implement recursion, so we must avoid using host
␈↓ αλinterrupts directly to implement interrupts.  We may not modify any register
␈↓ αλduring a host language interrupt, except one (such as **TICK**) which is


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl32␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλspecifically intended to signal interrupts.  Thus, if we were to add an
␈↓ αλinterrupt character facility to SCHEME similar to that in MacLISP [Moon], the
␈↓ αλMacLISP interrupt character function would merely set a register like **TICK**
␈↓ αλand dismiss; MLOOP would eventually notice that this register had changed and
␈↓ αλdispatch to the interrupt handler.  All this implies that the "microcode" for
␈↓ αλthe interrupt handlers does not itself contain critical code that must be
␈↓ αλprotected from host language interrupts.
␈↓ αhWhen the scheduler is invoked, if there is another process waiting on
␈↓ αλthe process queue, then the current process is swapped out and put on the end
␈↓ αλof the queue, and a new process swapped in from the front of the queue.  The
␈↓ αλprocess stored on the queue consists of an atom which has the current frame
␈↓ αλand **VAL** register on its property list.  Note that the **TEM** register is
␈↓ αλ␈↓¬␈↓'β␈↓'α saved, and so cannot be used to pass information between instructions.

␈↓ αλ␈↓↓(DEFUN SCHEDULE ()␈↓
␈↓ α\␈↓↓(COND (**QUEUE**␈↓
␈↓ β0␈↓↓(SWAPOUTPROCESS)␈↓
␈↓ β0␈↓↓(NCONC **QUEUE** (LIST **PROCESS**))␈↓
␈↓ β0␈↓↓(SETQ **PROCESS** (CAR **QUEUE**)␈↓
␈↓ βx␈↓↓**QUEUE** (CDR **QUEUE**))␈↓
␈↓ β0␈↓↓(SWAPINPROCESS)))␈↓
␈↓ α\␈↓↓(SETQ **TICK** NIL)␈↓
␈↓ α\␈↓↓(ALARMCLOCK 'RUNTIME **QUANTUM**))␈↓

␈↓ αλ␈↓↓(DEFUN SWAPOUTPROCESS ()␈↓
␈↓ α\␈↓↓((LAMBDA (**CLINK**)␈↓
␈↓ βH␈↓↓(PUTPROP **PROCESS** (SAVEUP **PC**) 'CLINK)␈↓
␈↓ βH␈↓↓(PUTPROP **PROCESS** **VAL** 'VAL))␈↓
␈↓ αh␈↓↓**CLINK**))␈↓

␈↓ αλ␈↓↓(DEFUN SWAPINPROCESS ()␈↓
␈↓ α\␈↓↓(SETQ **CLINK** (GET **PROCESS** 'CLINK)␈↓
␈↓ β$␈↓↓**VAL** (GET **PROCESS** 'VAL))␈↓
␈↓ α\␈↓↓(RESTORE))␈↓

␈↓ αhPrimitive operators are LISP functions, i.e. SUBRs, EXPRs, and LSUBRs.

␈↓ αλ␈↓↓(DEFUN PRIMOP (X) (GETL X '(SUBR EXPR LSUBR)))␈↓

␈↓ αhSAVEUP conses a new frame onto the **CLINK** structure.  It saves the
␈↓ αλvalues of all important registers.  It takes one argument, RETAG, which is the
␈↓ αλinstruction to return to when the computation is restored.

␈↓ αλ␈↓↓(DEFUN SAVEUP (RETAG)␈↓
␈↓ α\␈↓↓(SETQ **CLINK** (LIST **EXP** **UNEVLIS** **ENV** **EVLIS** RETAG **CLINK**)))␈↓

␈↓ αhRESTORE restores a computation from the CLINK.  The use of TEMP is a
␈↓ αλkludge to optimize the compilation of the "microcode".




␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl33␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλ␈↓↓(DEFUN RESTORE ()␈↓
␈↓ α ␈↓↓(PROG (TEMP)␈↓
␈↓ α\␈↓↓(SETQ TEMP (OR **CLINK**␈↓
␈↓ ∧∧␈↓↓(ERROR '|PROCESS RAN OUT - RESTORE|␈↓
␈↓ ∧d␈↓↓**EXP**␈↓
␈↓ ∧d␈↓↓'FAIL-ACT))␈↓
␈↓ β$␈↓↓**EXP** (CAR TEMP)␈↓
␈↓ β0␈↓↓TEMP (CDR TEMP)␈↓
␈↓ β$␈↓↓**UNEVLIS** (CAR TEMP)␈↓
␈↓ β0␈↓↓TEMP (CDR TEMP)␈↓
␈↓ β$␈↓↓**ENV** (CAR TEMP)␈↓
␈↓ β0␈↓↓TEMP (CDR TEMP)␈↓
␈↓ β$␈↓↓**EVLIS** (CAR TEMP)␈↓
␈↓ β0␈↓↓TEMP (CDR TEMP)␈↓
␈↓ β$␈↓↓**PC** (CAR TEMP)␈↓
␈↓ β0␈↓↓TEMP (CDR TEMP)␈↓
␈↓ β$␈↓↓**CLINK** (CAR TEMP))))␈↓

␈↓ αhThis is the central function of the SCHEME interpreter.  This
␈↓ αλ"instruction" expects **EXP** to contain an expression to evaluate, and
␈↓ αλ**ENV** to contain the environment for the evaluation.  The fact that we have
␈↓ αλarrived here indicates that **PC** contains 'AEVAL, and so we need not change
␈↓ αλ**PC** if the next instruction is also to be AEVAL.  Besides the obvious
␈↓ αλobjects likes numbers, identifiers, LAMBDA expressions, and BETA expressions
␈↓ αλ(closures), there are also several other objects of interest.  There are
␈↓ αλprimitive operators (LISP functions);  AINTs (which are to SCHEME as FSUBRs
␈↓ αλlike COND are to LISP);  and AMACROs, which are used to implement DO, AND, OR,
␈↓ αλCOND, BLOCK, etc.




␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl34␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλ␈↓↓(DEFUN AEVAL ()␈↓
␈↓ α\␈↓↓(COND ((ATOM **EXP**)␈↓
␈↓ β0␈↓↓(COND ((NUMBERP **EXP**)␈↓
␈↓ ∧∧␈↓↓(SETQ **VAL** **EXP**)␈↓
␈↓ ∧∧␈↓↓(RESTORE))␈↓
␈↓ βx␈↓↓((PRIMOP **EXP**)␈↓
␈↓ ∧∧␈↓↓(SETQ **VAL** **EXP**)␈↓
␈↓ ∧∧␈↓↓(RESTORE))␈↓
␈↓ βx␈↓↓((SETQ **TEM** (ASSQ **EXP** **ENV**))␈↓
␈↓ ∧∧␈↓↓(SETQ **VAL** (CADR **TEM**))␈↓
␈↓ ∧∧␈↓↓(RESTORE))␈↓
␈↓ βx␈↓↓(T (SETQ **VAL** (SYMEVAL **EXP**))␈↓
␈↓ ∧≤␈↓↓(RESTORE))))␈↓
␈↓ β$␈↓↓((ATOM (CAR **EXP**))␈↓
␈↓ β0␈↓↓(COND ((SETQ **TEM** (GET (CAR **EXP**) 'AINT))␈↓
␈↓ ∧∧␈↓↓(SETQ **PC** **TEM**))␈↓
␈↓ βx␈↓↓((EQ (CAR **EXP**) 'LAMBDA)␈↓
␈↓ ∧∧␈↓↓(SETQ **VAL** (LIST 'BETA **EXP** **ENV**))␈↓
␈↓ ∧∧␈↓↓(RESTORE))␈↓
␈↓ βx␈↓↓((SETQ **TEM** (GET (CAR **EXP**) 'AMACRO))␈↓
␈↓ ∧∧␈↓↓(SETQ **EXP** (FUNCALL **TEM** **EXP**)))␈↓
␈↓ βx␈↓↓(T (SETQ **EVLIS** NIL␈↓
␈↓ ∧d␈↓↓**UNEVLIS** **EXP**␈↓
␈↓ ∧d␈↓↓**PC** 'EVLIS))))␈↓
␈↓ β$␈↓↓((EQ (CAAR **EXP**) 'LAMBDA)␈↓
␈↓ β0␈↓↓(SETQ **EVLIS** (LIST (CAR **EXP**))␈↓
␈↓ βx␈↓↓**UNEVLIS** (CDR **EXP**)␈↓
␈↓ βx␈↓↓**PC** 'EVLIS))␈↓
␈↓ β$␈↓↓(T (SETQ **EVLIS** NIL␈↓
␈↓ ∧⊂␈↓↓**UNEVLIS** **EXP**␈↓
␈↓ ∧⊂␈↓↓**PC** 'EVLIS))))␈↓

␈↓ αhWe come to EVLIS when a combination is encountered.  The intention is to
␈↓ αλevaluate each component of the combination and then apply the resulting
␈↓ αλfunction to the resulting arguments.  We use the register **UNEVLIS** to hold
␈↓ αλthe list of components yet to be evaluated, and the register **EVLIS** to hold
␈↓ αλthe list of evaluated components.  We assume that these have been set up by
␈↓ αλAEVAL.  Note that in the case of an explicit LAMBDA expression in the CAR of a
␈↓ αλcombination **UNEVLIS** is initialized to be the list of unevaluated arguments
␈↓ αλand **EVLIS** is initialized to be the list containing the lambda expression.
␈↓ αhEVLIS checks to see if there remain any more components yet to be
␈↓ αλevaluated.  If not, it applies the function.  Note that the primitive
␈↓ αλoperators are applied using the LISP function APPLY.  Note also how a BETA
␈↓ αλexpression controls the environment in which its body is to be evaluated.
␈↓ αλDELTA expressions are CATCH tags (see CATCH).  It is interesting that the
␈↓ αλevaluated components are collected in the reverse order from that which we
␈↓ αλneed them in, and so we must reverse the list before applying the function.
␈↓ αλDo you see why we must not use side effects (e.g. the NREVERSE function) to
␈↓ αλreverse the list?  Think about CATCH!
␈↓ αhIf there remain components yet to be evaluated, EVLIS saves up a frame,


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl35␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλso that execution can be resumed at EVLIS1 when the evaluation of the
␈↓ αλcomponent returns with a value.  It then sets up **EXP** to point to the
␈↓ αλcomponent to be evaluated and dispatches to AEVAL.

␈↓ αλ␈↓↓(DEFUN EVLIS ()␈↓
␈↓ α\␈↓↓(COND ((NULL **UNEVLIS**)␈↓
␈↓ β0␈↓↓(SETQ **EVLIS** (REVERSE **EVLIS**))␈↓
␈↓ β0␈↓↓(COND ((ATOM (CAR **EVLIS**))␈↓
␈↓ ∧∧␈↓↓(SETQ **VAL** (APPLY (CAR **EVLIS**) (CDR **EVLIS**)))␈↓
␈↓ ∧∧␈↓↓(RESTORE))␈↓
␈↓ βx␈↓↓((EQ (CAAR **EVLIS**) 'LAMBDA)␈↓
␈↓ ∧∧␈↓↓(SETQ **ENV** (PAIRLIS (CADAR **EVLIS**) (CDR **EVLIS**) **ENV**)␈↓
␈↓ ∧L␈↓↓**EXP** (CADDAR **EVLIS**)␈↓
␈↓ ∧L␈↓↓**PC** 'AEVAL))␈↓
␈↓ βx␈↓↓((EQ (CAAR **EVLIS**) 'BETA)␈↓
␈↓ ∧∧␈↓↓(SETQ **ENV** (PAIRLIS (CADR (CADAR **EVLIS**))␈↓
␈↓ ε_␈↓↓(CDR **EVLIS**)␈↓
␈↓ ε_␈↓↓(CADDAR **EVLIS**))␈↓
␈↓ ∧L␈↓↓**EXP** (CADDR (CADAR **EVLIS**))␈↓
␈↓ ∧L␈↓↓**PC** 'AEVAL))␈↓
␈↓ βx␈↓↓((EQ (CAAR **EVLIS**) 'DELTA)␈↓
␈↓ ∧∧␈↓↓(SETQ **CLINK** (CADAR **EVLIS**))␈↓
␈↓ βx␈↓↓(RESTORE))␈↓
␈↓ βx␈↓↓(T (ERROR '|BAD FUNCTION - EVARGLIST| **EXP** 'FAIL-ACT))))␈↓
␈↓ β$␈↓↓(T (SAVEUP 'EVLIS1)␈↓
␈↓ βH␈↓↓(SETQ **EXP** (CAR **UNEVLIS**)␈↓
␈↓ ∧⊂␈↓↓**PC** 'AEVAL))))␈↓

␈↓ αhThe purpose of EVLIS1 is to gobble up the value, passed in the **VAL**
␈↓ αλregister, of the subexpression just evaluated.  It saves this value on the
␈↓ αλlist in the **EVLIS** register, pops off the unevaluated subexpression from
␈↓ αλthe **UNEVLIS** register, and dispatches back to EVLIS.

␈↓ αλ␈↓↓(DEFUN EVLIS1 ()␈↓
␈↓ α\␈↓↓(SETQ **EVLIS** (CONS **VAL** **EVLIS**)␈↓
␈↓ β$␈↓↓**UNEVLIS** (CDR **UNEVLIS**)␈↓
␈↓ β$␈↓↓**PC** 'EVLIS))␈↓

␈↓ αhHere is the code for the various AINTs.  On arrival at the instruction
␈↓ αλfor an AINT, **EXP** contains the expression whose functional position
␈↓ αλcontains the name of the AINT.  None of the arguments have been evaluated, and
␈↓ αλno new control frame has been created.  Note that each AINT is defined by the
␈↓ αλpresence of an AINT property on the property list of the LISP atom which is
␈↓ αλits name.  The value of this property is the LISP function which is the first
␈↓ αλ"instruction" of the AINT.

␈↓ αhEVALUATE is similar to the LISP function EVAL;  it evaluates its
␈↓ αλargument, which should result in a s-expression, which is then fed back into
␈↓ αλthe SCHEME expression evaluator (AEVAL).



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl36␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλ␈↓↓(DEFPROP EVALUATE EVALUATE AINT)␈↓

␈↓ αλ␈↓↓(DEFUN EVALUATE ()␈↓
␈↓ α\␈↓↓(SAVEUP 'EVALUATE1)␈↓
␈↓ α\␈↓↓(SETQ **EXP** (CADR **EXP**)␈↓
␈↓ β$␈↓↓**PC** 'AEVAL))␈↓

␈↓ αλ␈↓↓(DEFUN EVALUATE1 ()␈↓
␈↓ α\␈↓↓(SETQ **EXP** **VAL**␈↓
␈↓ β$␈↓↓**PC** 'AEVAL))␈↓

␈↓ αhIF evaluates its first argument, with a return address of IF1.  IF1
␈↓ αλexamines the resulting **VAL**, and gives either the second or third argument
␈↓ αλto AEVAL depending on whether the **VAL** was non-NIL or NIL.

␈↓ αλ␈↓↓(DEFPROP IF IF AINT)␈↓

␈↓ αλ␈↓↓(DEFUN IF ()␈↓
␈↓ α\␈↓↓(SAVEUP 'IF1)␈↓
␈↓ α\␈↓↓(SETQ **EXP** (CADR **EXP**)␈↓
␈↓ β$␈↓↓**PC** 'AEVAL))␈↓

␈↓ αλ␈↓↓(DEFUN IF1 ()␈↓
␈↓ α\␈↓↓(COND (**VAL** (SETQ **EXP** (CADDR **EXP**)))␈↓
␈↓ β$␈↓↓(T (SETQ **EXP** (CADDDR **EXP**))))␈↓
␈↓ α\␈↓↓(SETQ **PC** 'AEVAL))␈↓

␈↓ αhAs it was in the beginning, is now, and ever shall be:  QUOTE without
␈↓ αλend.  (Amen, amen.)

␈↓ αλ␈↓↓(DEFPROP QUOTE AQUOTE AINT)␈↓

␈↓ αλ␈↓↓(DEFUN AQUOTE ()␈↓
␈↓ α\␈↓↓(SETQ **VAL** (CADR **EXP**))␈↓
␈↓ α\␈↓↓(RESTORE))␈↓

␈↓ αhLABELS merely feeds its second argument to AEVAL after constructing a
␈↓ αλfiendishly clever environment structure.  This is done in two stages: first
␈↓ αλthe skeleton of the structure is created, with null environments in the
␈↓ αλclosures of the bound functions;  next the created environment is clobbered
␈↓ αλinto each of the closures.




␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl37␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλ␈↓↓(DEFPROP LABELS LABELS AINT)␈↓

␈↓ αλ␈↓↓(DEFUN LABELS ()␈↓
␈↓ α\␈↓↓(SETQ **TEM** (MAPCAR '(LAMBDA (DEF)␈↓
␈↓ ¬ ␈↓↓(LIST (CAR DEF)␈↓
␈↓ ¬h␈↓↓(LIST 'BETA (CADR DEF) NIL)))␈↓
␈↓ ∧4␈↓↓(CADR **EXP**)))␈↓
␈↓ α\␈↓↓(MAPC '(LAMBDA (VC) (RPLACA (CDDADR VC) **TEM**)) **TEM**)␈↓
␈↓ α\␈↓↓(SETQ **ENV** (NCONC **TEM** **ENV**)␈↓
␈↓ β$␈↓↓**EXP** (CADDR **EXP**)␈↓
␈↓ β$␈↓↓**PC** 'AEVAL))␈↓

␈↓ αhWe now come to the multiprocess primitives.
␈↓ αhCREATE!PROCESS temporarily creates a new set of machine registers (by
␈↓ αλthe lambda-binding mechanism of the ␈↓&host␈↓'β␈↓'α language), establishes the new
␈↓ αλprocess in those registers, swaps it out, and returns the new process id;
␈↓ αλreturning causes the old machine registers to be restored.

␈↓ αλ␈↓↓(DEFUN CREATE!PROCESS (EXP)␈↓
␈↓ αP␈↓↓((LAMBDA (**PROCESS** **EXP** **ENV** **UNEVLIS** **EVLIS** **PC** **CLINK** **VAL**)␈↓
␈↓ β<␈↓↓(SWAPOUTPROCESS)␈↓
␈↓ β<␈↓↓**PROCESS**)␈↓
␈↓ α\␈↓↓(GENSYM)␈↓
␈↓ α\␈↓↓EXP␈↓
␈↓ α\␈↓↓**ENV**␈↓
␈↓ α\␈↓↓NIL␈↓
␈↓ α\␈↓↓NIL␈↓
␈↓ α\␈↓↓'AEVAL␈↓
␈↓ α\␈↓↓(LIST NIL NIL NIL NIL 'TERMINATE NIL)␈↓
␈↓ α\␈↓↓NIL))␈↓

␈↓ αλ␈↓↓(DEFUN START!PROCESS (P)␈↓
␈↓ α\␈↓↓(COND ((OR (NOT (ATOM P)) (NOT (GET P 'CLINK)))␈↓
␈↓ β0␈↓↓(ERROR '|BAD PROCESS -- START!PROCESS| **EXP** 'FAIL-ACT)))␈↓
␈↓ α\␈↓↓(OR (EQ P **PROCESS**) (MEMQ P **QUEUE**)␈↓
␈↓ β␈↓↓(SETQ **QUEUE** (NCONC **QUEUE** (LIST P))))␈↓
␈↓ α\␈↓↓P)␈↓

␈↓ αλ␈↓↓(DEFUN STOP!PROCESS (P)␈↓
␈↓ αP␈↓↓(COND ((MEMQ P **QUEUE**)␈↓
␈↓ β$␈↓↓(SETQ **QUEUE** (DELQ P **QUEUE**)))␈↓
␈↓ β_␈↓↓((EQ P **PROCESS**) (TERMINATE)))␈↓
␈↓ αP␈↓↓P)␈↓

␈↓ αhTERMINATE is an internal microcode routine which terminates the current
␈↓ αλprocess.  If the current process is the only one, then all processes have been
␈↓ αλstopped, and so a new SCHEME top level is created;  otherwise TERMINATE pulls
␈↓ αλthe next process off the scheduler queue and swaps it in.  Note that we cannot
␈↓ αλuse SWAPINPROCESS because a RESTORE will happen in EVLIS as soon as TERMINATE
␈↓ αλcompletes (this is a very deep global property of the interpreter, and a fine


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl38␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλsource of bugs;  much care is required).

␈↓ αλ␈↓↓(DEFUN TERMINATE ()␈↓
␈↓ α\␈↓↓(COND ((NULL **QUEUE**)␈↓
␈↓ β0␈↓↓(SETQ **PROCESS**␈↓
␈↓ βx␈↓↓(CREATE!PROCESS '(**TOP** '|SCHEME -- QUEUEOUT|))))␈↓
␈↓ β$␈↓↓(T (SETQ **PROCESS** (CAR **QUEUE**)␈↓
␈↓ ∧⊂␈↓↓**QUEUE** (CDR **QUEUE**))))␈↓
␈↓ α\␈↓↓(SETQ **CLINK** (GET **PROCESS** 'CLINK))␈↓
␈↓ α\␈↓↓(SETQ **VAL** (GET **PROCESS** 'VAL))␈↓
␈↓ α\␈↓↓'TERMINATE-VALUE)␈↓

␈↓ αhEVALUATE!UNINTERRUPTIBLY merely binds the variable *ALLOW* to NIL, and
␈↓ αλthen evaluates its argument.  This is why this primitive follows the scoping
␈↓ αλrules for variables!

␈↓ αλ␈↓↓(DEFPROP EVALUATE!UNINTERRUPTIBLY EVALUATE!UNINTERRUPTIBLY AINT)␈↓

␈↓ αλ␈↓↓(DEFUN EVALUATE!UNINTERRUPTIBLY ()␈↓
␈↓ α\␈↓↓(SETQ **ENV** (CONS (LIST '*ALLOW* NIL) **ENV**)␈↓
␈↓ β$␈↓↓**EXP** (CADR **EXP**)␈↓
␈↓ β$␈↓↓**PC** 'AEVAL))␈↓

␈↓ αhDEFINE closes the function to be defined in the null environment, and
␈↓ αλinstalls the closure in the LISP value cell.

␈↓ αλ␈↓↓(DEFPROP DEFINE DEFINE AINT)␈↓

␈↓ αλ␈↓↓(DEFUN DEFINE ()␈↓
␈↓ α\␈↓↓(SET (CADR **EXP**) (LIST 'BETA (CADDR **EXP**) NIL))␈↓
␈↓ α\␈↓↓(SETQ **VAL** (CADR **EXP**))␈↓
␈↓ α\␈↓↓(RESTORE))␈↓

␈↓ αhASET looks up the specified variable in the current environment, and
␈↓ αλclobbers the value cell in the environment with the new value.  If the
␈↓ αλvariable is not bound in the current environment, the LISP value cell is set.
␈↓ αλNote that ASET does not need to be an AINT, since it does not fool with order
␈↓ αλof evaluation; all it needs is access to the "machine register" **ENV**.

␈↓ αλ␈↓↓(DEFUN ASET (VAR VALU)␈↓
␈↓ α\␈↓↓(SETQ **TEM** (ASSQ VAR **ENV**))␈↓
␈↓ α\␈↓↓(COND (**TEM** (RPLACA (CDR **TEM**) VALU))␈↓
␈↓ β$␈↓↓(T (SET VAR VALU)))␈↓
␈↓ α\␈↓↓VALU)␈↓

␈↓ αhCATCH binds the tag variable to a DELTA expression which contains the
␈↓ αλcurrent CLINK.  When AEVAL applies such an expression as a function (of one
␈↓ αλargument), it makes the **CLINK** in the DELTA expression be the **CLINK**,
␈↓ αλplaces the value of the argument in **VAL**, and does a RESTORE.  The effect
␈↓ αλis to return from the CATCH expression with the argument to the DELTA


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl39␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλexpression as its value (can you see why?).

␈↓ αλ␈↓↓(DEFPROP CATCH ACATCH AINT)␈↓

␈↓ αλ␈↓↓(DEFUN ACATCH ()␈↓
␈↓ α\␈↓↓(SETQ **ENV** (CONS (LIST (CADR **EXP**) (LIST 'DELTA **CLINK**)) **ENV**)␈↓
␈↓ β$␈↓↓**EXP** (CADDR **EXP**)␈↓
␈↓ β$␈↓↓**PC** 'AEVAL))␈↓

␈↓ αhPAIRLIS is as in the LISP 1.5 Programmer's Manual [McCarthy].

␈↓ αλ␈↓↓(DEFUN PAIRLIS (X Y Z)␈↓
␈↓ α\␈↓↓(DO ((I X (CDR I))␈↓
␈↓ β_␈↓↓(J Y (CDR J))␈↓
␈↓ β_␈↓↓(L Z (CONS (LIST (CAR I) (CAR J)) L)))␈↓
␈↓ β␈↓↓((AND (NULL I) (NULL J)) L)␈↓
␈↓ β␈↓↓(AND (OR (NULL I) (NULL J))␈↓
␈↓ β<␈↓↓(ERROR '|WRONG NUMBER OF ARGUMENTS - PAIRLIS|␈↓
␈↓ ∧⊂␈↓↓**EXP**␈↓
␈↓ ∧⊂␈↓↓'WRNG-NO-ARGS))))␈↓


␈↓ αhAMACROs are fairly complicated beasties, and have very little to do with
␈↓ αλthe basic issues of the implementation of SCHEME per se, so the code for them
␈↓ αλwill not be given here.  AMACROs behave almost exactly like MacLISP macros
␈↓ αλ[Moon].


␈↓ αλThis is the end of the SCHEME interpreter!



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl40␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλAcknowledgements



␈↓ αhThis paper would not have happened if Sussman had not been forced to
␈↓ αλthink about lambda calculus by having to teach 6.031, nor would it have
␈↓ αλhappened had not Steele been forced to understand PLASMA by morbid curiosity.
␈↓ αhThis work developed out of an initial attempt to understand the
␈↓ αλactorness of actors.  Steele thought he understood it, but couldn't explain
␈↓ αλit;  Sussman suggested the experimental approach of actually building an
␈↓ αλ"ACTORS interpreter".  This interpreter attempted to intermix the use of
␈↓ αλactors and LISP lambda expressions in a clean manner.  When it was completed,
␈↓ αλwe discovered that the "actors" and the lambda expressions were identical in
␈↓ αλimplementation.  Once we had discovered this, all the rest fell into place,
␈↓ αλand it was only natural to begin thinking about actors in terms of lambda
␈↓ αλcalculus.  The original interpreter was call-by-name for various reasons
␈↓ αλhaving to do with 6.031; we subsequently experimentally discovered how call-
␈↓ αλby-name screws iteration, and rewrote it to use call-by-value.  Note well that
␈↓ αλwe did ␈↓¬␈↓'β␈↓'α bring forth a clean implementation in one brilliant flash of
␈↓ αλunderstanding;  we used an experimental and highly empirical approach to
␈↓ αλbootstrap our knowledge.
␈↓ αhWe wish to thank the staff of 6.031, Mike Dertouzos, and Steve Ward, for
␈↓ αλprecipitating this intellectual adventure.  Carl Hewitt spent many hours
␈↓ αλexplaining the innards and outards of PLASMA to Steele over the course of
␈↓ αλseveral months;  Marilyn McClennan was also helpful in this respect.  Brian
␈↓ αλSmith and Richard Zippel helped a lot.  We wish to thank Seymour Papert, Ben
␈↓ αλKuipers, Marvin Minsky, and Vaughn Pratt for their excellent suggestions.



␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl41␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλBibliography



␈↓ αλ[Bobrow and Wegbreit]
␈↓ αhBobrow, Daniel G. and Wegbreit, Ben.  "A Model and Stack Implementation
␈↓ αλof Multiple Environments."  CACM 16, 10 (October 1973) pp. 591-603.

␈↓ αλ[Church]
␈↓ αhChurch, Alonzo.  ␈↓&The Calculi of Lambda Conversion␈↓'β␈↓'α.  Annals of
␈↓ αλMathematics Studies Number 6.  Princeton University Press (Princeton, 1941).
␈↓ αλReprinted by Klaus Reprint Corp. (New York, 1965).

␈↓ αλ[Dijkstra]
␈↓ αhDijkstra, Edsger W.  "Solution of a Problem in Concurrent Programming
␈↓ αλControl."  CACM 8,9 (September 1965) p. 569.

␈↓ αλ[Fischer]
␈↓ αhFischer, Michael J.  "Lambda Calculus Schemata." Proceedings of ACM
␈↓ αλConference on Proving Assertions about Programs.  SIGPLAN Notices (January
␈↓ αλ1972).

␈↓ αλ[Galley and Pfister]
␈↓ αhGalley, S.W. and Pfister, Greg.  ␈↓&The MDL Language␈↓'β␈↓'α.  Programming
␈↓ αλTechnology Division Document SYS.11.01.  Project MAC, MIT (Cambridge, November
␈↓ αλ1975).

␈↓ αλ[Greif]
␈↓ αhGreif, Irene.  ␈↓&Semantics of Communicating Parallel Processes␈↓'β␈↓'α.  Ph.D.
␈↓ αλthesis.  MAC-TR-154, Project MAC, MIT (Cambrudge, September 1975).

␈↓ αλ[Greif and Hewitt]
␈↓ αhGreif, Irene and Hewitt, Carl.  ␈↓&Actor Semantics of Planner-73␈↓'β␈↓'α.  Working
␈↓ αλPaper 81, MIT AI Lab (Cambridge, 1975).

␈↓ αλ[Ingerman]
␈↓ αhIngerman, P. Z.  "Thunks -- A Way of Compiling Procedure Statements with
␈↓ αλSome Comments on Procedure Declarations." CACM 4,1 (January 1961) pp. 55-58.

␈↓ αλ[Knuth]
␈↓ αhKnuth, Donald E.  "Additional Comments on a Problem in Concurrent
␈↓ αλProgramming Control."  CACM 9,5 (May 1966) pp. 321-322.

␈↓ αλ[Lamport]
␈↓ αhLamport, Leslie.  "A New Solution of Dijkstra's Concurrent Programming
␈↓ αλProblem."  CACM 17,8 (August 1974) pp. 453-455.

␈↓ αλ[MAC]
␈↓ αh␈↓&Project MAC Progress Report XI (July 1973 - July 1974)␈↓'β␈↓'α.  Project MAC,
␈↓ αλMIT (Cambridge, 1974).


␈↓ αλ␈↓&␈↓↓Sussman and Steele    December 29, 1975␈↓ εl42␈↓ πXImplementation of the Interpreter␈↓'β␈↓'α␈↓








␈↓ αλ[McCarthy]
␈↓ αhMcCarthy, John, et al.  ␈↓&LISP 1.5 Programmer's Manual␈↓'β␈↓'α.  The MIT Press
␈↓ αλ(Cambridge, 1965).

␈↓ αλ[McDermott and Sussman]
␈↓ αhMcDermott, Drew V. and Sussman, Gerald Jay.  ␈↓&The CONNIVER Reference␈↓'β␈↓'α
␈↓ αλ␈↓&Manual␈↓'β␈↓'α.  AI Memo 295a.  MIT AI Lab (Cambridge, January 1974).

␈↓ αλ[Moon]
␈↓ αhMoon, David A.  ␈↓&MACLISP Reference Manual, Revision 0␈↓'β␈↓'α.  Project MAC, MIT
␈↓ αλ(Cambridge, April 1974).

␈↓ αλ[Moses]
␈↓ αhMoses, Joel.  ␈↓&The Function of FUNCTION in LISP␈↓'β␈↓'α.  AI Memo 199, MIT AI Lab
␈↓ αλ(Cambridge, June 1970).

␈↓ αλ[Reynolds]
␈↓ αhReynolds, John C.  "Definitional Interpreters for Higher Order
␈↓ αλProgramming Languages." ACM Conference Proceedings 1972.

␈↓ αλ[Smith and Hewitt]
␈↓ αhSmith, Brian C. and Hewitt, Carl.  ␈↓&A PLASMA Primer␈↓'β␈↓'α (draft).  MIT AI Lab
␈↓ αλ(Cambridge, October 1975).

␈↓ αλ[Sussman]
␈↓ αhSussman, Gerald Jay, Winograd, Terry, and Charniak, Eugene.  ␈↓&Micro-␈↓'β␈↓'α
␈↓ αλ␈↓&PLANNER Reference Manual␈↓'β␈↓'α.  AI Memo 203A.  MIT AI Lab (Cambridge, December
␈↓ αλ1971).

ββββ